LeetCode

Binary Tree Level Order Traversal II

2014.1.8 01:45

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

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

return its bottom-up level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Solution:

　　This is a variation from: LeetCode - Binary Tree Level Order Traversal.

　　Level-order traversal of a binary tree can be done with stl-queue. But in this problem it can be done with preorder traversal, too.

　　When the traversal is done, reverse the result by row and you get what you need.

　　Time and space complexities are both O(n), where n is the number of nodes in the tree. Space complexity comes from the local parameters passed in function calls.

Accepted code:

 1 // 1CE, 1AC, when copying the code, make sure you don't mix up the name of function and variables!!
 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     //1CE here, levelOrder, levelOrderBottom, check the names before you copy the codes!!!!
14     // That was stupid, man~
15     vector<vector<int> > levelOrderBottom(TreeNode *root) {
16         // IMPORTANT: Please reset any member data you declared, as
17         // the same Solution instance will be reused for each test case.
18         // I could use pre-order traversal to do this.
19         // Level-order traversal makes sense too.
20         
21         // 1CE here, declaration of int i is MISSSING
22         for(int i = 0; i < result.size(); ++i){
23             result[i].clear();
24         }
25         result.clear();
26         
27         if(root == nullptr){
28             return result;
29         }
30         
31         preOrder(root, 0);
32 
33         vector<int> tmp;
34         int i = 0;
35         while(i < result.size() - 1 - i){
36             tmp = result[i];
37             result[i] = result[result.size() - 1 - i];
38             result[result.size() - 1 - i] = tmp;
39             ++i;
40         }
41         return result;
42     }
43 private:
44     vector<vector<int>> result;
45     
46     void preOrder(TreeNode *root, int height) {
47         if(root == nullptr){
48             return;
49         }
50         // 1CE here,  ) MISSING!!!
51         while(result.size() <= height){
52             result.push_back(vector<int>());
53         }
54         result[height].push_back(root->val);
55         
56         if(root->left != nullptr){
57             preOrder(root->left, height + 1);
58         }
59         if(root->right != nullptr){
60             // 1CE here, spelling error, pre-order preOrder
61             // Don't rely on auto-complete, you're spoiled!!!
62             preOrder(root->right, height + 1);
63         }
64     }
65 };