当前位置:网站首页>LeetCode 0107.二叉树的层序遍历II - 另一种方法
LeetCode 0107.二叉树的层序遍历II - 另一种方法
2022-07-05 05:45:00 【Tisfy】
【LetMeFly】107.二叉树的层序遍历 II
力扣题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
给你二叉树的根节点 root
,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
示例 1:
输入: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
方法一:优先队列
与之前方法不同,这次决定不使用pair<TreeNode*, int>
,而是直接使用TreeNode*
入队。
看不懂的可以先看之前这篇博客:https://letmefly.blog.csdn.net/article/details/125584554
那么,没有了int
类型的层数,怎么判断哪些节点是属于同一层的呢?
其实也很简单,我们在队列不空的时候,记录下来队列中一共由多少个元素,这些元素的个数就是当前最后一层的节点的个数。
然后,我们用一个循环,把这些元素全都添加到答案的同一层中(同时把子节点入队)即可。
- 时间复杂度 O ( N ) O(N) O(N),其中 N N N是节点个数。
- 空间复杂度 O ( N 2 ) O(N2) O(N2),其中 N 2 N2 N2是节点最多的一层的节点数。
AC代码
C++
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ans;
queue<TreeNode*> q;
if (root)
q.push(root);
int layer = -1;
while (q.size()) {
ans.push_back({
});
layer++;
int thisLayerNum = q.size();
while (thisLayerNum--) {
TreeNode* thisNode = q.front();
q.pop();
ans[layer].push_back(thisNode->val);
if (thisNode->left)
q.push(thisNode->left);
if (thisNode->right)
q.push(thisNode->right);
}
}
reverse(ans.begin(), ans.end()); // 注意,这里是本题要求从最后一层开始遍历,所以reverse了以下。正常情况下的层次遍历是不需要reverse的
return ans;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/125610699
边栏推荐
- Detailed explanation of expression (csp-j 2021 expr) topic
- shared_ Repeated release heap object of PTR hidden danger
- 注解与反射
- PC寄存器
- Solution to the palindrome string (Luogu p5041 haoi2009)
- 使用Electron开发桌面应用
- 【Jailhouse 文章】Jailhouse Hypervisor
- 挂起等待锁 vs 自旋锁(两者的使用场合)
- Sword finger offer 58 - ii Rotate string left
- The number of enclaves
猜你喜欢
Little known skills of Task Manager
API related to TCP connection
AtCoder Grand Contest 013 E - Placing Squares
Some common problems in the assessment of network engineers: WLAN, BGP, switch
Solution to game 10 of the personal field
剑指 Offer 09. 用两个栈实现队列
R language [import and export of dataset]
F - Two Exam(AtCoder Beginner Contest 238)
Hang wait lock vs spin lock (where both are used)
剑指 Offer 58 - II. 左旋转字符串
随机推荐
How to adjust bugs in general projects ----- take you through the whole process by hand
Sword finger offer 53 - ii Missing numbers from 0 to n-1
常见的最优化方法
Haut OJ 2021 freshmen week II reflection summary
Control unit
In this indifferent world, light crying
剑指 Offer 58 - II. 左旋转字符串
过拟合与正则化
【云原生】微服务之Feign自定义配置的记录
从Dijkstra的图灵奖演讲论科技创业者特点
Mysql database (I)
shared_ Repeated release heap object of PTR hidden danger
The connection and solution between the shortest Hamilton path and the traveling salesman problem
Software test -- 0 sequence
Sword finger offer 09 Implementing queues with two stacks
全国中职网络安全B模块之国赛题远程代码执行渗透测试 //PHPstudy的后门漏洞分析
R语言【数据集的导入导出】
2022 极术通讯-Arm 虚拟硬件加速物联网软件开发
Fried chicken nuggets and fifa22
二十六、文件系统API(设备在应用间的共享;目录和文件API)