[leetcode] 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],
]

与[leetcode] Binary Tree Level Order Traversal的方法相同，利用一个队列来完成层次遍历，最后在把结果反转过来即可。

代码如下：

 1 /**
 2  * Definition for binary tree
 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         // Note: The Solution object is instantiated only once and is reused by each test case.
14        
15         vector<vector<int>> result;
16         vector<vector<int>> result2;
17         if(root==NULL) return result;
18         vector<int> temp;
19         queue<TreeNode * > q;
20         q.push(NULL);
21         q.push(root);
22         while(q.size()>1)
23         {
24             if(q.front()==NULL)
25             {
26                 q.pop();
27                 q.push(NULL);
28                 if(temp.size()!=0) result.push_back(temp);
29                 temp.clear();
30             }
31             else
32             {
33                 if(q.front()->left!=NULL)q.push(q.front()->left);
34                 if(q.front()->right!=NULL)q.push(q.front()->right);
35                 temp.push_back(q.front()->val);
36                 q.pop();
37             }
38         }
39         if(temp.size()!=0) result.push_back(temp);
40         for(int i = result.size() - 1; i >= 0; i--) result2.push_back(result.at(i));
41         return result2;
42         
43     }
44 };