leetcode 42：binary-tree-level-order-traversal-ii

题目描述

给定一个二叉树，返回该二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）

例如：

给定的二叉树是{3,9,20,#,#,15,7},

    3↵   / ↵  9  20↵    /  ↵   15   7

该二叉树由底层到顶层层序遍历的结果是

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

如果你不清楚“{1,#,2,3}"的含义的话，请继续阅读

OJ用这样的方法将二叉树序列化：

二叉树的序列化遵循层序遍历的原则，”#“代表该位置是一条路径的终结，下面不再存在结点。

例如：

   1↵  / ↵ 2   3↵    /↵   4↵    ↵     5

上述的二叉树序列化的结果是："{1,2,3,#,#,4,#,#,5}".

题目分析：

树的层序遍历，常规题。这里需要处理一下返回值的顺序。

代码如下：

 1  vector<vector<int> > levelOrderBottom(TreeNode* root) {
 2         vector<vector<int>> vret;
 3         if(root == NULL)
 4             return vret;
 5         stack<vector<int>> ret;
 6         queue<TreeNode*> stk;
 7         stk.push(root);
 8         while(!stk.empty())
 9         {
10             int size = stk.size();
11             vector<int> tmp;
12             for(int i = 0;i < size;i++)
13             {
14                 TreeNode* front = stk.front();
15                 tmp.push_back(front->val);
16                 stk.pop();
17                 if(front->left != NULL)
18                     stk.push(front->left);
19                 if(front->right != NULL)
20                     stk.push(front->right);
21             }
22             ret.push(tmp);
23         }
24         while(!ret.empty())
25         {
26             vret.push_back(ret.top());
27             ret.pop();
28         }
29         return vret;
30     }