Leetcode刷题java之103. 二叉树的锯齿形层次遍历

向右看齐 2023-07-11 06:13 11阅读 0赞

执行结果：

通过

显示详情

执行用时 :1 ms, 在所有 Java 提交中击败了98.62% 的用户

内存消耗 :38.5 MB, 在所有 Java 提交中击败了5.16%的用户

题目：

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

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

3  
/ \\  
9 20  
/ \\  
15 7

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

每一回合反转list，而不是反转队列。

代码：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            List<List<Integer>> result=new ArrayList<>();
            LinkedList<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            boolean reverse=false;
            while(queue.size()!=0)
            {
                List<Integer> list=new ArrayList<>();
                int count=queue.size();
                while(count-->0)
                {
                    TreeNode node=queue.poll();
                    if(node==null)
                    {
                        continue;
                    }
                    list.add(node.val);
                    queue.add(node.left);
                    queue.add(node.right);
                }
                if(reverse)
                {
                    Collections.reverse(list);
                }
                reverse=!reverse;
                if(list.size()>0)
                {
                    result.add(list);
                }
            }
            return result;
        }
    }