LeetCode 数据结构与算法之二叉树的锯齿形层序遍历

简介: LeetCode 数据结构与算法之二叉树的锯齿形层序遍历

题目


二叉树的锯齿形层序遍历


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


示例 1:


image.png


输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]


示例 2:


输入:root = [1]
输出:[[1]]


示例 3:


输入:root = []
输出:[]


提示:


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


题解


解题分析


解题思路


  1. 本题目可以采用广度优先搜索,对树进行逐层遍历,用队列维护当前层的所有元素,当队列不为空的时候,求得当前队列的长度 size,每次从队列中取出 size 个元素进行拓展,然后进行下一次迭代。


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


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


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


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


复杂度


时间复杂度 O(N)


空间复杂度 O(N)


解题代码


题解代码如下(代码中有详细的注释说明):


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        // 1. 判断是否为空
        if (root == null) {
            return ans;
        }
        // queue 实现 bfs 按层遍历
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;
        while(!nodeQueue.isEmpty()) {
            // 定义双端队列存储当前层的值
            Deque<Integer> levelList = new LinkedList<Integer>();
            // 获取当前层的个数
            int size = nodeQueue.size();
            // 遍历队列中该层的值并且出队,按照标志位存入双端队列,再按照固定循序读取下一层
            for (int i =0; i< size; i++) {
                // 获取节点
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    // 顺序存
                    levelList.offerLast(curNode.val);
                } else {
                    // 反向存
                    levelList.offerFirst(curNode.val);
                }
                // 获取下一层节点值(从左往右)
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                } 
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            // 标志位转换
            isOrderLeft = !isOrderLeft;
        }
        return ans;
    }
}


提交后反馈结果(由于该题目没有进行优化,性能一般):


image.png


参考信息



相关文章
|
8天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
40 5
|
8天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
2月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
93 4
|
2月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
2月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
66 5
|
2月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
49 0
|
3月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
99 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
3月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
50 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
3月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
39 0
数据结构与算法学习十四:常用排序算法总结和对比