Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >二叉树的锯齿形层序遍历

二叉树的锯齿形层序遍历

作者头像
狼啸风云
发布于 2024-01-28 01:44:52
发布于 2024-01-28 01:44:52
12900
代码可运行
举报
运行总次数:0
代码可运行

给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:root = [1]
输出:[[1]]

示例 3:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

方法

此题是「102. 二叉树的层序遍历」的变种,最后输出的要求有所变化,要求我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第0层,如果当前层数是偶数,从左至右输出当前层的节点值,否则,从右至左输出当前层的节点值。

我们依然可以沿用第 102 题的思想,修改广度优先搜索,对树进行逐层遍历,用队列维护当前层的所有元素,当队列不为空的时候,求得当前队列的长度\textit{size},每次从队列中取出 \textit{size}个元素进行拓展,然后进行下一次迭代。

为了满足题目要求的返回值为「先从左往右,再从右往左」交替输出的锯齿形,我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。

双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展,但是对当前层节点的存储我们维护一个变量 \textit{isOrderLeft}记录是从左至右还是从右至左的:

如果从左至右,我们每次将被遍历到的元素插入至双端队列的末尾。

如果从右至左,我们每次将被遍历到的元素插入至双端队列的头部。

当遍历结束的时候我们就得到了答案数组。

代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) {
            return ans;
        }

        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);
        bool isOrderLeft = true;

        while (!nodeQueue.empty()) {
            deque<int> levelList;
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                auto node = nodeQueue.front();
                nodeQueue.pop();
                if (isOrderLeft) {
                    levelList.push_back(node->val);
                } else {
                    levelList.push_front(node->val);
                }
                if (node->left) {
                    nodeQueue.push(node->left);
                }
                if (node->right) {
                    nodeQueue.push(node->right);
                }
            }
            ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }
};

复杂度分析

时间复杂度:O(N),其中N为二叉树的节点数。每个节点会且仅会被遍历一次。

空间复杂度:O(N)。我们需要维护存储节点的队列和存储节点值的双端队列,空间复杂度为 O(N)。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-01-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
☆打卡算法☆LeetCode 103、二叉树的锯齿形层序遍历 算法解析
链接:103. 二叉树的锯齿形层序遍历 - 力扣(LeetCode) (leetcode-cn.com)
恬静的小魔龙
2022/08/07
2110
☆打卡算法☆LeetCode 103、二叉树的锯齿形层序遍历  算法解析
Leetcode No.103 二叉树的锯齿形层序遍历
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
week
2021/11/29
1840
【栈与队列】N叉树的层序遍历 && 二叉树的锯齿形层序遍历
​ 这道题其实就是 二叉树的层序遍历 的变形,只不过将其左右孩子改成了一个数组来存放孩子节点罢了,我们只需要遍历一下数组即可,其它思路都是一样的,就是使用队列的先进先出特点,每次处理一层,然后根据队列的元素个数控制每层遍历d
利刃大大
2025/02/23
540
【栈与队列】N叉树的层序遍历 && 二叉树的锯齿形层序遍历
二叉树的5种遍历方式
锯齿形层序遍历:层序遍历的变种,要求我们按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第 0 层,如果当前层数是偶数,从左至右输出当前层的节点值,否则,从右至左输出当前层的节点值。
伊泽瑞尔
2022/06/01
1.7K0
二叉树的5种遍历方式
二叉树的前序、中序、后序、层序以及蛇形遍历的实现方式
如上述所示,蛇形层次遍历的顺序为:先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行。
CG国斌
2020/05/21
9620
LeetCode 二叉树的锯齿形层次遍历(二叉树)(BFS)
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如: 给定二叉树 [3,9,20,null,null,15,7],
SakuraTears
2022/01/13
2020
leetcode-103二叉树的锯齿形层序遍历「建议收藏」
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
全栈程序员站长
2022/09/22
1330
leetcode刷题(81)——103. 二叉树的锯齿形层次遍历
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
老马的编程之旅
2022/06/22
2890
leetcode刷题(81)——103. 二叉树的锯齿形层次遍历
算法刷题-二叉树的锯齿形层序遍历、用栈实现队列 栈设计、买卖股票的最佳时机 IV
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
共饮一杯无
2023/02/13
2380
【Leetcode】103. 二叉树的锯齿形层次遍历
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
Leetcode名企之路
2019/03/11
9560
双端队列解决
给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
狼啸风云
2023/11/22
1130
双端队列解决
【一天一大 lee】二叉树的锯齿形层序遍历 (难度:中等) - Day20201222
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
前端小书童
2021/01/05
2740
103. 二叉树的锯齿形层序遍历
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如: 给定二叉树 [3,9,20,null,null,15,7] c
编程张无忌
2021/07/20
1780
103. 二叉树的锯齿形层序遍历
图解LeetCode第 103 号问题:二叉树的锯齿形层次遍历
返回其层次遍历结果: [ [3], [20,9], [15,7] ]
五分钟学算法
2018/12/25
8030
2021-10-06:二叉树的锯齿形层序遍历。给定一个二叉树,返
2021-10-06:二叉树的锯齿形层序遍历。给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。力扣103。
福大大架构师每日一题
2021/10/06
1860
LeetCode 103. 二叉树的锯齿形层次遍历(BFS / 双栈)
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
Michael阿明
2020/07/13
3790
LeetCode 103. 二叉树的锯齿形层次遍历(BFS / 双栈)
LeetCode 103. 二叉树的锯齿形层次遍历
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
手撕代码八百里
2020/07/28
3770
LeetCode 103. 二叉树的锯齿形层次遍历
每日一题:LeetCode-103/107.二叉树的(层序/锯齿形层序)遍历
   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,日日累积,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️
用户11029129
2024/06/04
920
每日一题:LeetCode-103/107.二叉树的(层序/锯齿形层序)遍历
Leetcode | 第8节:记忆化搜索,树(上)
今天我们来讲一讲记忆化搜索和树这个数据结构。记忆化搜索是对搜索算法的一个优化,涉及到记忆化搜索的题目都或多或少有一点技巧。至于树,它的定义非常简单,也有非常多的应用。同时它自己也在查找和排序中有自己的用武之地(例如二叉搜索树)。因此树的内容比较多也比较杂,我们可能没有办法一节给它说明白,也希望大家具备一些耐心~
学弱猹
2021/08/10
3830
Leetcode | 第8节:记忆化搜索,树(上)
LeetCode57|二叉树的锯齿形层次遍历
写了一年的文章了,整体输出文章内容基本上都是以java为主,大概篇幅内容都是围绕着数据库,JDK源码,mybatis,spring,springboot的框架来进行输出的,一年有所成长,有所失去,快到十一了,去年也是十一的时候开始了文章输出的,一年的时间过得好快啊
码农王同学
2020/09/21
2840
LeetCode57|二叉树的锯齿形层次遍历
推荐阅读
相关推荐
☆打卡算法☆LeetCode 103、二叉树的锯齿形层序遍历 算法解析
更多 >
领券
💥开发者 MCP广场重磅上线!
精选全网热门MCP server,让你的AI更好用 🚀
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验