70 二叉树的层次遍历 II

原题网址：http://www.lintcode.com/zh-cn/problem/binary-tree-level-order-traversal-ii/

给出一棵二叉树，返回其节点值从底向上的层次序遍历（按从叶节点所在层到根节点所在的层遍历，然后逐层从左往右遍历）

您在真实的面试中是否遇到过这个题？

Yes

样例

给出一棵二叉树 {3,9,20,#,#,15,7},

按照从下往上的层次遍历为：

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

标签

队列二叉树二叉树遍历宽度优先搜索

思路：此前做过二叉树的层次遍历，代码大致相同，只是多设置了一个栈存储每层节点数值的数组，遍历完二叉树后，将栈中数组压入结果数组中就OK了。

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 
14 class Solution {
15 public:
16     /**
17      * @param root: A tree
18      * @return: buttom-up level order a list of lists of integer
19      */
20     vector<vector<int>> levelOrderBottom(TreeNode * root) {
21         // write your code here
22         vector<vector<int>> result;
23      if (root==NULL)
24      {
25          return result;
26      }
27      stack<vector<int>> s;
28      queue<TreeNode *> level;
29      level.push(root);
30      int len; //计数器，记录每层节点数量;
31 
32      while(!level.empty())
33      {
34          len=level.size();
35          vector<int> temp;
36          while(len--) //遍历当前层数值，并将当前层节点的左右孩子入队列;
37          {
38              TreeNode *p=level.front();
39              level.pop();
40              temp.push_back(p->val);
41              if (p->left!=NULL)
42              {
43                  level.push(p->left);
44              }
45              if (p->right!=NULL)
46              {
47                  level.push(p->right);
48              }
49          }
50          s.push(temp);
51      }
52      while(!s.empty())
53      {
54          vector<int> t=s.top();
55          result.push_back(t);
56          s.pop();
57      }
58      return result;
59     }
60 };

另一种方法：用两个vector代替queue保存层节点。

注：翻转数组时可使用reverse（）函数。

 1 /**
 2  * Definition of TreeNode:
 3  * class TreeNode {
 4  * public:
 5  *     int val;
 6  *     TreeNode *left, *right;
 7  *     TreeNode(int val) {
 8  *         this->val = val;
 9  *         this->left = this->right = NULL;
10  *     }
11  * }
12  */
13 
14 class Solution {
15 public:
16     /**
17      * @param root: A tree
18      * @return: buttom-up level order a list of lists of integer
19      */
20     vector<vector<int>> levelOrderBottom(TreeNode * root) {
21         // write your code here
22         vector<vector<int>> result;
23      if (root==NULL)
24      {
25          return result;
26      }
27      vector<vector<TreeNode *>> levelNode; //所有层节点;
28      vector<TreeNode *> preLevelNode;
29      preLevelNode.push_back(root);
30      levelNode.push_back(preLevelNode);
31 
32      while(!preLevelNode.empty())
33      {
34          vector<TreeNode *> curLevelNode;
35          for (int i=0;i<(int)preLevelNode.size();i++)
36          {
37              TreeNode *p=preLevelNode[i];
38              if (p->left!=NULL)
39              {
40                  curLevelNode.push_back(p->left);
41              }
42              if (p->right!=NULL)
43              {
44                  curLevelNode.push_back(p->right);
45              }
46          } 
47          levelNode.push_back(curLevelNode);
48          preLevelNode.assign(curLevelNode.begin(),curLevelNode.end());
49      }
50      levelNode.pop_back();//注意最后一次压入的是空数组，所以循环终止，遍历时应剔除尾部的空数组;
51      for (int i=levelNode.size()-1;i>=0;i--)
52      {
53          vector<int> temp;
54          for (int j=0;j<(int)levelNode[i].size();j++)
55          {
56              temp.push_back(levelNode[i][j]->val);
57          }
58          result.push_back(temp);
59      }
60      return result;
61     }
62 };