LintCode领扣 题解丨 微软常考题:二叉树的锯齿形层次遍历

简介: LintCode领扣 题解丨 微软常考题:二叉树的锯齿形层次遍历

给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)

在线评测地址:https://www.lintcode.com/problem/binary-tree-zigzag-level-order-traversal/?utm_source=sc-tianchi-sz0818

样例 1:

输入:{1,2,3}
输出:[[1],[3,2]]
解释:

1

/ \
2 3
它将被序列化为 {1,2,3}
样例 2:

输入:{3,9,20,#,#,15,7}
输出:[[3],[20,9],[15,7]]
解释:

3

/ \
9 20

/  \

15 7
它将被序列化为 {3,9,20,#,#,15,7}
【题解】

算法:树的层次遍历

层次遍历,可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历,开辟一个新队列,让头结点入队并计算此时的长度,每次都将当前层的子节点全部压入队列,然后对下一层的节点进行遍历,再将下一层的子节点压入队列,不断循环,一直遍历到底层,判断的终止条件就是队列不为空。

循环里面,队列头出队,判断其是否有左右子结点,如果有,则将此点的子节点入队,但此时还不需要更新队列的长度,当前队列的长度是每层的长度。当这层的长度减为0时,就说明这层的遍历结束,开始更新长度为下一层的长度。
出队的元素的值按照一层层压入结果数组
因为题目锯齿形遍历
我们用一个isforward标记当前方向,每遍历完一层,如果是反向的,则将这层的节点数组倒序,然后将这层的集合压入结果
复杂度分析

时间复杂度O(n)
n为节点数量
空间复杂度O(n)
存下所有点的信息 n为节点数量
public class Solution
{

/**
 * @param root: A Tree
 * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
 */
public List<List<Integer>> zigzagLevelOrder(TreeNode root){
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    //正反向标志
    boolean isForward = true;
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> subList = new ArrayList<Integer>();
        for (int i = 0 ; i < size ; i++) {
            TreeNode treeNode = q.poll();
            subList.add(treeNode.val);
            if (treeNode.left != null) { 
                q.offer(treeNode.left);
            }
            if (treeNode.right != null) {
                q.offer(treeNode.right);
            }
        }
        //根据标志来确认当前层遍历的方向
        if (!isForward) {
            Collections.reverse(subList);//翻转
        }
        ans.add(subList);
        //方向反转
        isForward = !isForward;
    }
    return ans;
}

}
更多题解参见:给出一棵二叉树,返回其节点值的锯齿形层次遍历(先从左往右,下一层再从右往左,层与层之间交替进行)

在线评测地址:

LintCode 领扣
​
www.lintcode.com
样例 1:

输入:{1,2,3}
输出:[[1],[3,2]]
解释:

1

/ \
2 3
它将被序列化为 {1,2,3}
样例 2:

输入:{3,9,20,#,#,15,7}
输出:[[3],[20,9],[15,7]]
解释:

3

/ \
9 20

/  \

15 7
它将被序列化为 {3,9,20,#,#,15,7}
【题解】

算法:树的层次遍历

层次遍历,可以运用广度遍历的思想实现从上往下的逐层遍历。从头结点开始逐层遍历,开辟一个新队列,让头结点入队并计算此时的长度,每次都将当前层的子节点全部压入队列,然后对下一层的节点进行遍历,再将下一层的子节点压入队列,不断循环,一直遍历到底层,判断的终止条件就是队列不为空。

循环里面,队列头出队,判断其是否有左右子结点,如果有,则将此点的子节点入队,但此时还不需要更新队列的长度,当前队列的长度是每层的长度。当这层的长度减为0时,就说明这层的遍历结束,开始更新长度为下一层的长度。
出队的元素的值按照一层层压入结果数组
因为题目锯齿形遍历
我们用一个isforward标记当前方向,每遍历完一层,如果是反向的,则将这层的节点数组倒序,然后将这层的集合压入结果
复杂度分析

时间复杂度O(n)
n为节点数量
空间复杂度O(n)
存下所有点的信息 n为节点数量
public class Solution
{

/**
 * @param root: A Tree
 * @return: A list of lists of integer include the zigzag level order traversal of its nodes' values.
 */
public List<List<Integer>> zigzagLevelOrder(TreeNode root){
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    if (root == null) {
        return ans;
    }
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    //正反向标志
    boolean isForward = true;
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> subList = new ArrayList<Integer>();
        for (int i = 0 ; i < size ; i++) {
            TreeNode treeNode = q.poll();
            subList.add(treeNode.val);
            if (treeNode.left != null) { 
                q.offer(treeNode.left);
            }
            if (treeNode.right != null) {
                q.offer(treeNode.right);
            }
        }
        //根据标志来确认当前层遍历的方向
        if (!isForward) {
            Collections.reverse(subList);//翻转
        }
        ans.add(subList);
        //方向反转
        isForward = !isForward;
    }
    return ans;
}

}
更多题解参见九章算法官网:
https://www.jiuzhang.com/solution/binary-tree-zigzag-level-order-traversal/?utm_source=sc-tianchi-sz0818

相关文章
|
网络协议 网络架构
华为--路由器配置DHCP小实验
华为--路由器配置DHCP小实验
1038 0
华为--路由器配置DHCP小实验
|
3天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
1661 2
|
6天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
6天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
3天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
3177 0
|
19天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
8547 58
|
13天前
|
Linux 开发工具 iOS开发
2026最新codex下载安装保姆级使用教程(下载+安装+登录+使用,含所有历史版本)
本文详解OpenAI Codex国内快速上手指南:提供Win/macOS/Linux全平台免安装包、npm/Homebrew等多方式安装、账号/API Key双登录、简体中文切换,覆盖下载、安装、汉化、使用及高频避坑(如微软商店失败、npm超时等),10分钟即可跑通。
3034 9
|
19天前
|
JavaScript API iOS开发
DeepSeek Harness下载、安装、配置一篇搞定(2026整理,送常用插件)
DeepSeek Harness(DSH)是DeepSeek于2026年开源的MIT协议AI Agent框架,支持插件化组装模型、工具、沙箱与UI,兼容主流大模型。本文提供免Node.js的桌面端安装包(Win/macOS),含详细图文教程及热门插件推荐。
5814 69
|
7天前
|
云安全 人工智能 安全