LeetCode-107:二叉树的层次遍历II
一、题目描述
-
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
-
例如:给定二叉树
[3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为:
[
[15,7],
[9,20],
[3]
]
二、解题方法
这是一系列的问题。共同点为二叉树按层次遍历,把每层的元素区分开来。
核心步骤是你怎么确定每层的最后一个元素是哪个
我们可以利用队列进行二叉树的层次遍历,注意当每次重新进入while
循环时,队列里的数据就是二叉树当前这一层的节点个数。那么我们取个auto len = queue.size()
,把前len
个数据加入vector
,就可以了。
三、完整代码
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> Q;
vector<int> tmp;
vector<vector<int>> sln;
if(!root) return sln;
Q.push(root);
while(!Q.empty()){
auto size = Q.size();
for(int i = 0; i < size; i++){
auto ins = Q.front();
Q.pop();
tmp.push_back(ins->val);
if(ins->left)
Q.push(ins->left);
if(ins->right)
Q.push(ins->right);
}
sln.push_back(tmp);
tmp.clear();
}
reverse(sln.begin(), sln.end());
return sln;
}
};