Powered By GitBook
107.Binary Tree Level Order Traversal II
难度:Easy

107.Binary Tree Level Order Traversal II

给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
1
例如:
2
给定二叉树 [3,9,20,null,null,15,7],
3
4
3
5
/ \
6
9 20
7
/ \
8
15 7
9
返回其自底向上的层次遍历为:
10
11
[
12
[15,7],
13
[9,20],
14
[3]
15
]
Copied!
类似于429题的N叉树的层次遍历。代码如下:
1
/**
2
* Definition for a binary tree node.
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
deque<TreeNode*> dt;
14
vector<vector<int>> res;
15
if(!root) return res;
16
dt.push_back(root);
17
while(!dt.empty())
18
{
19
vector<int> tmp;
20
for(auto i:dt)
21
tmp.push_back(i->val);
22
int len=dt.size();
23
while(len--){
24
if(dt[0]->left)
25
dt.push_back(dt[0]->left);
26
if(dt[0]->right)
27
dt.push_back(dt[0]->right);
28
dt.pop_front();
29
}
30
// cout<<dt.size()<<endl;
31
32
33
res.push_back(tmp);
34
35
36
}
37
reverse(res.begin(),res.end());
38
return res;
39
40
}
41
};
Copied!
Last modified 2yr ago