力扣刷题：二叉树的锯齿形层次遍历（java实现）

zone 发布于2021-11-16 11:44 / 2535人阅读

摘要：题目给定一个二叉树，返回其节点值的锯齿形层序遍历。即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。

题目：给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

返回锯齿形层序遍历如下：

[
[3],
[20,9],
[15,7]
]

相关标签：树、广度优先搜索、二叉树

解析：题目要求按照层数的奇偶来存储数据的顺序，可以考虑双端队列，根据层数来将元素的值添加到队头或者队尾,，再用一个队列来维护当前层的结点。具体代码如下:

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {        List<List<Integer>> lists = new LinkedList<>();        if(root == null){            return lists;        }        //创建一个队列用于存放每一层的结点        Queue<TreeNode> queue = new LinkedList<>();        queue.offer(root);//初始的时候添加根结点        boolean sign = true;//用于区分奇偶层        while (!queue.isEmpty()){            //获取队列的长度            int size = queue.size();            //创建一个双端队列用于存储该层的结点值            Deque<Integer> res = new LinkedList<>();            for (int i = 0; i < size; i++) {                //获取队头结点                TreeNode curNode = queue.poll();                //根据层数来判断添加到队头还是队尾                if(sign){                    res.offerLast(curNode.val);                }else {                    res.offerFirst(curNode.val);                }                //更新结点队列                if(curNode.left!=null){                    queue.offer(curNode.left);                }                if(curNode.right!=null){                    queue.offer(curNode.right);                }            }            //添加到结果集里面            lists.add(new LinkedList<>(res));            //改变层数状态            sign = !sign;        }        return lists;    }

解法不唯一，如果有错误，欢迎指正~

idc机房托管云服务器二叉树的遍历 java二叉树的构建二叉树的存储二叉树的存储结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123455.html

【Leetcode】103. 二叉树的锯齿形层次遍历

摘要：题目给定一个二叉树，返回其节点值的锯齿形层次遍历。例如给定二叉树返回锯齿形层次遍历如下题解这道题要求用字型就是要求知道深度。稍作改动的是需要在遍历左子树和右子树的时候带上深度的信息，才能知道是加在列表头还是列表尾部。题目给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。例如：给定二叉树 [3,9,20,null...

XiNGRZ 2019-08-16 15:23 评论0 收藏0
力扣(LeetCode)103

摘要：题目地址题目描述给定一个二叉树，返回其节点值的锯齿形层次遍历。即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。解答二叉树的层序遍历，只不过对于偶数层来说，把该层的遍历结果转置一下就行了。题目地址：https://leetcode-cn.com/probl...题目描述：给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类...

ZHAO_ 2019-08-16 14:33 评论0 收藏0
LeetCode通关：连刷三十九道二叉树，刷疯了！⭐四万字长文搞定二叉树，建议收藏！⭐

分门别类刷算法，坚持，进步！刷题路线参考：https://github.com/youngyangyang04/leetcode-master 大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们收藏一下。二叉树基础二叉树是一种比较常见的数据结构，在开始刷二叉树...

honhon 2021-09-04 16:45 评论0 收藏0
＜LeetCode天梯＞Day031 验证二叉搜索树（递归+中序遍历） | 初级算法 | Pytho

摘要：有效二叉搜索树定义如下节点的左子树只包含小于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值，因此中序遍历以后得到的序列一定是升序序列。 ...

Genng 2021-11-24 09:39 评论0 收藏0
力扣(LeetCode)513

摘要：示例输入输出示例输入输出注意您可以假设树即给定的根节点不为。解答我们只需要层次遍历从左到右这个二叉树，并且用每层第一个节点的值替换临时变量。就能得到正确的结果，注意的是树的层次遍历需要用到队列代码题目地址：https://leetcode-cn.com/probl...题目描述：给定一个二叉树，在树的最后一行找到最左边的值。示例 1: 输入: 2 / 1 3 输出:1 示例...

Leck1e 2019-08-16 14:27 评论0 收藏0