107. 二叉树的层序遍历 II
给你二叉树的根节点 root
,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
示例 1:
![](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)
输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
提示:
- 树中节点数目在范围
[0, 2000]
内 -1000 <= Node.val <= 1000
题解
思路和力扣 103. 二叉树的锯齿形层序遍历 [内存优化], 很相似,实验了queue
,最后选用vector
替代queue
。
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if(root==nullptr){
return res;
}
vector<TreeNode*> arr;//记录每层节点(会一直更新和清理旧节点)
arr.emplace_back(root);
while(!arr.empty()){
int len=arr.size();
int *layer=new int[len];
vector<TreeNode *> tmp;//记录下一层节点
int cnt=0;
for (auto& node : arr) {//当前层节点遍历
layer[cnt++]=node->val;
if (node->left) {
tmp.emplace_back(node->left);
}
if (node->right) {
tmp.emplace_back(node->right);
}
}
res.emplace_back((vector<int>){layer,layer+len});
arr = move(tmp);//将下一层节点全部移动给arr
}
reverse(res.begin(),res.end());
return res;
}
};
标签:node,arr,遍历,res,层序,II,二叉树,root,节点 From: https://www.cnblogs.com/fudanxi/p/16832113.html