Leetcode No.103 二叉树的锯齿形层序遍历
2023-03-20 14:55:53 时间
一、题目描述
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如: 给定二叉树 [3,9,20,null,null,15,7],
3 / 9 20 / 15 7 返回锯齿形层序遍历如下:
[ [3], [20,9], [15,7] ]
二、解题思路
此题是「102. 二叉树的层序遍历」的变种,最后输出的要求有所变化,要求我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第 0 层,如果当前层数是偶数,从左至右输出当前层的节点值,否则,从右至左输出当前层的节点值。
我们依然可以沿用第 102 题的思想,修改广度优先搜索,对树进行逐层遍历,用队列维护当前层的所有元素,当队列不为空的时候,求得当前队列的长度size,每次从队列中取出size 个元素进行拓展,然后进行下一次迭代。
为了满足题目要求的返回值为「先从左往右,再从右往左」交替输出的锯齿形,我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。
双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展,但是对当前层节点的存储我们维护一个变量 revese 记录是从左至右还是从右至左的:
如果从左至右,我们每次将被遍历到的元素插入至双端队列的末尾。
如果从右至左,我们每次将被遍历到的元素插入至双端队列的头部。
当遍历结束的时候我们就得到了答案数组。
三、代码
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> rs=new ArrayList<>();
if(root==null){
return rs;
}
Queue<TreeNode> queue=new ArrayDeque();
queue.add(root);
int revese=-1;
while(!queue.isEmpty()){
int n=queue.size();
List<Integer> level=new ArrayList<>();
for(int i=0;i<n;i++){
TreeNode parent=queue.poll();
if(parent.left!=null){
queue.add(parent.left);
}
if(parent.right!=null){
queue.add(parent.right);
}
level.add(parent.val);
if(i==n-1){
revese*=-1;
if(revese==-1){
Collections.reverse(level);
}
rs.add(level);
}
}
}
return rs;
}
}
四、复杂度分析
时间复杂度:O(N),其中 N 为二叉树的节点数。每个节点会且仅会被遍历一次。
空间复杂度:O(N)。我们需要维护存储节点的队列和存储节点值的双端队列,空间复杂度为 O(N)。
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十