LeetCode

2014.1.1 01:53

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution:

　　Level-order traversal of a binary tree is usually performed with BFS and queue. But the return result of this problem is a bit special, we can do it with pre-order traversal as well. The difference is that you calculate the result data in a different order, but same output at last.

　　Time complexity is O(n), space complexiy is O(1), where n is the number of nodes in the tree.

Accepted code:

 1 // 3CE, 1AC, you fool!!! The code must be bug-free, well.. at least it should compile and runnnnnnnnnnn!
 2 /**
 3  * Definition for binary tree
 4  * struct TreeNode {
 5  *     int val;
 6  *     TreeNode *left;
 7  *     TreeNode *right;
 8  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 9  * };
10  */
11 class Solution {
12 public:
13     vector<vector<int> > levelOrder(TreeNode *root) {
14         // IMPORTANT: Please reset any member data you declared, as
15         // the same Solution instance will be reused for each test case.
16         // I could use pre-order traversal to do this.
17         // Level-order traversal makes sense too.
18         
19         // 1CE here, declaration of int i is MISSSING
20         for(int i = 0; i < result.size(); ++i){
21             result[i].clear();
22         }
23         result.clear();
24         
25         if(root == nullptr){
26             return result;
27         }
28         
29         preOrder(root, 0);
30         return result;
31     }
32 private:
33     vector<vector<int>> result;
34     
35     void preOrder(TreeNode *root, int height) {
36         if(root == nullptr){
37             return;
38         }
39         // 1CE here,  ) MISSING!!!
40         while(result.size() <= height){
41             result.push_back(vector<int>());
42         }
43         result[height].push_back(root->val);
44         
45         if(root->left != nullptr){
46             preOrder(root->left, height + 1);
47         }
48         if(root->right != nullptr){
49             // 1CE here, spelling error, pre-order preOrder
50             // Don't rely on auto-complete, you're spoiled!!!
51             preOrder(root->right, height + 1);
52         }
53     }
54 };