题目描述
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)。
来源,leetcode 每日一题 107. 二叉树的层次遍历Ⅱ
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为:
[
[15,7],
[9,20],
[3]
]
解题思路
- 层次遍历,使用队列,将每层节点按序加载进来。
- 自底向上输出:反序遍历结果。
代码
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> answer;
if (root == NULL) {
return answer;
}
queue<TreeNode*> que1;
que1.push(root);
int times = 0;
while (times == 0 || !que1.empty()) {
vector<int> temp;
queue<TreeNode*> que2;
while (!que1.empty()) { // 队列不空
TreeNode* node = que1.front();
que1.pop();
if (node->left != NULL) {
que2.push(node->left);
}
if (node->right != NULL) {
que2.push(node->right);
}
temp.push_back(node->val);
}
answer.push_back(temp);
que1 = que2;
times++;
}
reverse(answer.begin(), answer.end());
return answer;
}
};