题目简介：
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：
给定二叉树 [3,9,20,null,null,15,7],
返回其自底向上的层次遍历为：
1
2
3
4
5
| [
[15,7],
[9,20],
[3]
]
|
思路：
广搜，最后将数组倒置即可。
需要注意的是每次出队前需提前将当前的队列大小记录下来(也就是这层有多少元素)。
tip:
代码如下：
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if(!root)
return {};
vector<vector<int>> res;
queue<TreeNode*> qu;
qu.push(root);
while(!qu.empty()){
vector<int> temp;
int size = qu.size();
for(int i = 0; i < size; i++){
TreeNode* top = qu.front();
qu.pop();
temp.push_back(top -> val);
if(top -> left)
qu.push(top -> left);
if(top -> right)
qu.push(top -> right);
}
res.push_back(temp);
}
reverse(res.begin(), res.end());
return res;
}
};
|
