103. 二叉树的锯齿形层序遍历【191】

Love The Way You Lie 2023-09-26 22:20 3阅读 0赞

> **难度等级：中等**

> **上一篇算法：**
> 
> [104. 二叉树的最大深度【75】][104. _75]

> **力扣此题地址：**
> 
> [103. 二叉树的锯齿形层序遍历 - 力扣（Leetcode）][103. _ - _Leetcode]

## 1.题目：103. 二叉树的锯齿形层序遍历 ##

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

![5ebdf9ba29474a3fadff7abfb274ecc7.png][]

## 2.解题思路： ##

> 本题的解决思路和[102. 二叉树的层序遍历【206】][102. _206] 类似，可以说思路基本一样，只是在一个细节的地方不一样。遍历完一层后，添加元素到链表中，可以选择添加到链表尾部还是头部，偶数层的话（即0、2、4）就添加到尾部，这样就是从左到右遍历；奇数层的话（即1、3、5）就添加到头部，这样就相当于从右往左遍历。
> 
> 实现锯齿形层序遍历的方法，本质上其实就是在添加元素的时候选择插入到链表尾部还是头部。
> 
> **具体思路：**
> 
> 1.按层数的奇偶来决定每一层的输出顺序。规定二叉树的根节点为第0 层，如果当前层数是偶数，**从左至右**输出当前层的节点值，否则，**从右至左**输出当前层的节点值。
> 
> 2.我们依然可以沿用第 102 题的思想，修改广度优先搜索，对树进行逐层遍历，用队列维护当前层的所有元素，当队列不为空的时候，求得当前队列的长度size，每次从队列中取出 size个元素进行拓展，然后进行下一次迭代。
> 
> 3.为了满足题目要求的返回值为「先从左往右，再从右往左」交替输出的锯齿形，我们可以利用「双端队列」的数据结构来维护当前层节点值输出的顺序。
> 
> 4.双端队列是一个可以在队列任意一端插入元素的队列。在广度优先搜索遍历当前层节点拓展下一层节点的时候我们仍然从左往右按顺序拓展，但是对当前层节点的存储我们维护一个boolean类型的变量 isOrderLeft，记录是从左至右还是从右至左的：
> 
> \*如果从左至右，我们每次将被遍历到的元素插入至双端队列的末尾。
> 
> \*如果从右至左，我们每次将被遍历到的元素插入至双端队列的头部。
> 
> 当遍历结束的时候我们就得到了答案数组。

> **思路参考：**[103. 二叉树的锯齿形层序遍历 - 力扣（Leetcode）][103. _ - _Leetcode 1]

## 3.代码实现： ##

/**
     * 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<List<Integer>> ans = new LinkedList<List<Integer>>();
            
            if(root == null){
                return ans;
            }
    
            //创建一个队列，用于存放树的结点，结点的出队入队
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
            queue.add(root);
            boolean isOrderLeft = true;
    
            while(!queue.isEmpty()){
                //声明一个双端队列，用于接收结点，双端队列可以从尾部添加元素，也可以从头部添加元素
                //队列的实现有两种，数组和链表都可以实现队列
                Deque<Integer> list = new LinkedList<Integer>();
                int size = queue.size();
                
                for(int i=0;i<size;i++){
                    //当前结点出队
                    TreeNode curNode = queue.poll();
                    //如果isOrderLeft为true，说明是偶数，则从左到右添加元素
                    //如果isOrderLeft为false，说明是奇数，则从右到左添加元素
                    if(isOrderLeft){
                        list.offerLast(curNode.val);
                    }else{
                        list.offerFirst(curNode.val);
                    }
    
                    //每出一个节点，对应的将其左右子节点添加到队列中
                    if(curNode.left != null){
                        queue.add(curNode.left);
                    }
                    if(curNode.right != null){
                        queue.add(curNode.right);
                    }
                }
                //将这一层被遍历的结点值放入列表中
                ans.add(new LinkedList<Integer>(list));
                //对isOrderLeft赋值，下一次遍历则反过来遍历
                isOrderLeft = !isOrderLeft;
            }
            return ans;
        }
    }

[104. _75]: https://blog.csdn.net/m0_51697147/article/details/130319450?spm=1001.2014.3001.5501
[103. _ - _Leetcode]: https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
[5ebdf9ba29474a3fadff7abfb274ecc7.png]: https://img-blog.csdnimg.cn/5ebdf9ba29474a3fadff7abfb274ecc7.png
[102. _206]: https://blog.csdn.net/m0_51697147/article/details/130280896?spm=1001.2014.3001.5501
[103. _ - _Leetcode 1]: https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/solutions/530400/er-cha-shu-de-ju-chi-xing-ceng-xu-bian-l-qsun/