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

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

Hide Tags

Tree Breadth-first Search

这题其实就是一个二叉树的广度搜索，然后就是reverse。

写了两个，一个整个树用vector 记录，然后行之间用NULL 标记，然后再填回去，不过这样很耗空间，本来这样写是为了不想使用reverse，后面发现还是使用比较好。

 1 class Solution {
 2 public:
 3     vector<vector<int> > levelOrderBottom(TreeNode *root) {
 4         vector<vector<int> >ret;
 5         if(root==NULL)  return ret;
 6         vector<int> line;
 7         vector<TreeNode *> que;
 8         TreeNode * curNode;
 9         int idx= 0;
10         que.push_back(root);
11         que.push_back(NULL);
12         while(idx+1<que.size()){
13             curNode=que[idx];
14             if(curNode!=NULL){
15                 if(curNode->left!=NULL) que.push_back(curNode->left);
16                 if(curNode->right!=NULL)    que.push_back(curNode->right);
17             }
18             else{
19                 if(idx+1<que.size())
20                     que.push_back(NULL);
21             }
22             idx++;
23         }
24         for(idx--,line.clear();idx>=0;idx--){
25             curNode = que[idx];
26             if(curNode==NULL){
27                 reverse(line.begin(),line.end());
28                 ret.push_back(line);
29                 line.clear();
30             }
31             else{
32                 line.push_back(curNode->val);
33             }
34         }
35         ret.push_back(line);
36         return ret;
37     }
38 };

View Code

另外一个就是，标准的queue 广度搜索，queque 中存一行的全部node ，然后利用当前行的node 数，边写var 边填入queque ，不过不是外部循环，利用node 处理方便很多，下面代码就是用了外部循环，没有那么简洁：

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <iterator>
  6 using namespace std;
  7 
  8 
  9 ///Definition for binary tree
 10 struct TreeNode {
 11     int val;
 12     TreeNode *left;
 13     TreeNode *right;
 14     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 15 };
 16 /***
 17 class Solution {
 18 public:
 19     vector<vector<int> > levelOrderBottom(TreeNode *root) {
 20         vector<vector<int> >ret;
 21         if(root==NULL)  return ret;
 22         vector<int> line;
 23         vector<TreeNode *> que;
 24         TreeNode * curNode;
 25         int idx= 0;
 26         que.push_back(root);
 27         que.push_back(NULL);
 28         while(idx+1<que.size()){
 29             curNode=que[idx];
 30             if(curNode!=NULL){
 31                 if(curNode->left!=NULL) que.push_back(curNode->left);
 32                 if(curNode->right!=NULL)    que.push_back(curNode->right);
 33             }
 34             else{
 35                 if(idx+1<que.size())
 36                     que.push_back(NULL);
 37             }
 38             idx++;
 39         }
 40         for(idx--,line.clear();idx>=0;idx--){
 41             curNode = que[idx];
 42             if(curNode==NULL){
 43                 reverse(line.begin(),line.end());
 44                 ret.push_back(line);
 45                 line.clear();
 46             }
 47             else{
 48                 line.push_back(curNode->val);
 49             }
 50         }
 51         ret.push_back(line);
 52         return ret;
 53     }
 54 };
 55 */
 56 class Solution {
 57 public:
 58     vector<vector<int> > levelOrderBottom(TreeNode *root) {
 59         vector<vector<int> >ret;
 60         if(root==NULL)  return ret;
 61         vector<int> line;
 62         queue<TreeNode *> que;
 63         TreeNode * curNode;
 64         que.push(root);
 65         que.push(NULL);
 66         while(que.size()>1){
 67             curNode=que.front();
 68             que.pop();
 69             if(curNode==NULL){
 70                 ret.push_back(line);
 71                 line.clear();
 72                 que.push(NULL);
 73                 continue;
 74             }
 75             line.push_back(curNode->val);
 76             if(curNode->left!=NULL) que.push(curNode->left);
 77             if(curNode->right!=NULL)    que.push(curNode->right);
 78 
 79         }
 80         ret.push_back(line);
 81         reverse(ret.begin(),ret.end());
 82         return ret;
 83     }
 84 };
 85 
 86 
 87 
 88 
 89 int main()
 90 {
 91     Solution sol;
 92     TreeNode node1(1);
 93     TreeNode node2(2);
 94     TreeNode node3(3);
 95     TreeNode node4(4);
 96     node1.right=&node2;
 97     node2.left =&node3;
 98     node2.right =&node4;
 99 
100     vector<vector<int> >ret =sol.levelOrderBottom(&node1);
101     for(int i=0;i<ret.size();i++){
102         copy(ret[i].begin(),ret[i].end(),ostream_iterator<int>(cout," "));
103         cout<<endl;
104     }
105 
106 
107     return 0;
108 }

View Code

discuss 中有另外一个历史dfs 实现的，思路其实差不多，dfs 中每次遍历的值先填写到vector<vector<int> > ret正确位置，即一列一列地填，而bfs 则是一行一行地填ret，最后反向一下，仍然是不能避免反向。

下面是代码，直接copy一下了：

https://oj.leetcode.com/discuss/5353/there-better-regular-level-order-traversal-reverse-result

 1 vector<vector<int> > res;
 2 
 3 void DFS(TreeNode* root, int level)
 4 {
 5     if (root == NULL) return;
 6     if (level == res.size()) // The level does not exist in output
 7     {
 8         res.push_back(vector<int>()); // Create a new level
 9     }
10 
11     res[level].push_back(root->val); // Add the current value to its level
12     DFS(root->left, level+1); // Go to the next level
13     DFS(root->right,level+1);
14 }
15 
16 vector<vector<int> > levelOrderBottom(TreeNode *root) {
17     DFS(root, 0);
18     return vector<vector<int> > (res.rbegin(), res.rend());
19 }

View Code

[LeetCode] Binary Tree Level Order Traversal II

推荐阅读