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,null,null,15,7],
return its bottom-up level order traversal as:
1
2
3
4
5
| [
[15,7],
[9,20],
[3]
]
|
题意理解
给定一个二叉树，要求自底向上，自左向右的按层输出二叉树各节点的值。输出保存在一个二维数组中，也就是一个数组的数组，外层数组的元素是二叉树每一层节点的值的集合。
解法思路
解法一：DFS（Depth-First-Search）
可以知道的是，输出的二维数组中用一个数组来保存二叉树中的每一层的节点的值，且该内层数组在外层数组中的下标索引刚好与这些节点在树中的高度相反。所以可以利用 DFS 来遍历二叉树，根据节点在树中的高度，找到数组中保存该层元素的内层数组，将节点的值插入，最后只需将整个数组反转即可。对于二叉树的深度优先搜索，可以考虑用递归或者栈来实现。
DFS with recursive：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
levelRecursive(res, root, 0);
reverse(res.begin(), res.end());
return res;
}
void levelRecursive(vector<vector<int>> &res, TreeNode* root, int level){
if (root == NULL)
return ;
if (res.size() < level+1){
vector<int> vec;
res.push_back(vec);
}
res[level].push_back(root->val);
levelRecursive(res, root->left, level+1);
levelRecursive(res, root->right, level+1);
}
};
|
DFS with stack：
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
| class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL)
return res;
vector<pair<TreeNode*, int>> stack;
stack.push_back({root, 0});
while (!stack.empty()){
pair<TreeNode*, int> p = stack.back();
stack.pop_back();
if (res.size() < p.second + 1){
vector<int> vec;
res.push_back(vec);
}
res[p.second].push_back(p.first->val);
if (p.first->right != NULL)
stack.push_back({p.first->right, p.second+1});
if (p.first->left != NULL)
stack.push_back({p.first->left, p.second+1});
}
reverse(res.begin(), res.end());
return res;
}
};
|
解法二：BFS（Breadth-First-Search）
使用队列来存放每一层的节点，在 while 循环中又有一个 for 循环来遍历每一层的元素。
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
| class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode* > q;
if (root == NULL)
return res;
q.push(root);
while (!q.empty()){
vector<int> level;
int len = q.size();
for (int i = 0; i < len; ++i){
level.push_back(q.front()->val);
TreeNode* p = q.front();
q.pop();
if (p->left != NULL)
q.push(p->left);
if (p->right != NULL)
q.push(p->right);
}
res.push_back(level);
}
reverse(res.begin(), res.end());
return res;
}
};
|
复杂度：以上解法的时间复杂度及空间复杂度都为 O(N)。