Binary Tree Level Order Traversal II (Easy)

Description

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).

1
2
3
4
5
6
7
8
9
10
11
12
13
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

Analysis

我的方法比较愚蠢= =。先dfs出最大深度，再来就好办了。。

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//C++
class Solution {
    vector<vector<int> >ans;
    int maxdepth = 0;
    void dfsmaxdep(TreeNode *root,int depth){
        if(root==NULL)
        {
            if(depth>maxdepth)
                maxdepth = depth;
            return;
        }
        dfsmaxdep(root->left,depth+1);
        dfsmaxdep(root->right,depth+1);
    }

    void dfsans(TreeNode *root,int depth){
        if(root==NULL)
            return;
        ans[maxdepth-1-depth].push_back(root->val);
        if(root->left) dfsans(root->left,depth+1);
        if(root->right) dfsans(root->right,depth+1);
    }
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        if(root==NULL)
            return ans;
        dfsmaxdep(root,0);
        ans.resize(maxdepth);
        dfsans(root,0);
        return ans;
    }
};