Binary Tree Level Order Traversal II

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.

Analyse: same as the solutions in Binary Tree Level Order Traversal except we need to reverse the sequence in the vector.

1. Recursion.

　 Runtime: 4ms.

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> levelOrderBottom(TreeNode* root) {
13         vector<vector<int> > result;
14         if(!root) return result;
15         traverse(root, 0, result);
16         for(int i = 0, j = result.size() - 1; i < j; i++, j--){
17             swap(result[i], result[j]);
18         }
19         return result;
20     }
21     void traverse(TreeNode* root, int level, vector<vector<int> >& result){
22         if(!root) return;
23         if(level == result.size()) //current level does not exsit, we need to create it
24             result.push_back(vector<int> ());
25         
26         result[level].push_back(root->val); //push the node in the level
27         traverse(root->left, level + 1, result);
28         traverse(root->right, level + 1, result);
29     }
30 };

2. Iteration.

　Runtime: 8ms.

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     vector<vector<int>> levelOrderBottom(TreeNode* root) {
13         vector<vector<int> >result;
14         if(!root) return result;
15         queue<TreeNode* > qu;
16         qu.push(root);
17         
18         while(!qu.empty()){
19             int n = qu.size();
20             vector<int> level; //store the nodes value in current level
21             while(n--){
22                 TreeNode* temp = qu.front();
23                 level.push_back(temp->val);
24                 qu.pop();
25                 
26                 if(temp->left) qu.push(temp->left);
27                 if(temp->right) qu.push(temp->right);
28             }
29             result.push_back(level);
30         }
31         
32         for(int i = 0, j = result.size() - 1; i < j; i++, j--) 
33             swap(result[i], result[j]);
34         
35         return result;
36     }
37 };