LeetCode-103. Binary Tree Zigzag Level Order Traversal-CSDN博客

本文链接：https://blog.csdn.net/lemon2631/article/details/78163181

该博客介绍了如何实现LeetCode中的103题，即二叉树的锯齿形层次遍历。给出了通过单队列结合`Collections.reverse()`方法的解题思路，并提供了相关代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

算法描述

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

解题思路

按“之”字形打印树中的元素，可以通过单队列+collections.reverse()实现；或者通过单队列（通过变量判断是前插后读，还是前读后插）；如果采用递归的方式，也是类似的思路，根据变量判断是从前面插入元素还是从后面插入元素。

代码

单队列+Collections.reverse()的方式实现

/**
 * 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<List<Integer>>();
        if(root == null)
            return result;
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        //Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.add(root);
        int round = 0;
        while(queue1.size()!=0 ){
            List<Integer> local = new ArrayList<Integer>();
            int size = queue1.size();
            for(int i=0;i<size;i++){
                TreeNode tmp = queue1.poll();
                local.add(tmp.val);
                if(tmp.left != null)
                    queue1.add(tmp.left);
                if(tmp.right != null)
                    queue1.add(tmp.right);
            }
            if(round % 2 == 1)
                Collections.reverse(local);

            result.add(local);
            round++;
        }
        return result;
    }
}