Leetcode No.103 二叉树的锯齿形层序遍历

week

发布于 2021-11-29 14:20:41

1520

发布于 2021-11-29 14:20:41

文章被收录于专栏：用户画像用户画像

一、题目描述

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

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

3 / \ 9 20 / \ 15 7 返回锯齿形层序遍历如下：

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

二、解题思路

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

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

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

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

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

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

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

三、代码

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rs=new ArrayList<>();
        if(root==null){
            return rs;
        }
        Queue<TreeNode> queue=new ArrayDeque();
        queue.add(root);
        int revese=-1;
        while(!queue.isEmpty()){
            int n=queue.size();
            List<Integer> level=new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode parent=queue.poll();
                if(parent.left!=null){
                    queue.add(parent.left);
                }
                if(parent.right!=null){
                    queue.add(parent.right);
                }
                level.add(parent.val);
                if(i==n-1){
                    revese*=-1;
                    if(revese==-1){
                        Collections.reverse(level);
                    }
                    rs.add(level);
                }
            }
        }
        return rs;
    }
}