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

查看题目

中等

树

二叉树

广度优先搜索

高频

解法一：广度优先遍历

时间复杂度：O(n) | 空间复杂度：O(n) | 推荐使用

动画演示

二叉树结构:

准备就绪 - 输入二叉树结构，然后点击开始

代码实现

/**
 * 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;
 *     }
 * }
 */

import java.util.*;

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

**算法思路：** 使用广度优先遍历（BFS）实现二叉树的锯齿形层序遍历。 1. **基本思想**：利用队列进行层序遍历，每遍历一层时，根据标志位决定遍历方向 2. **队列使用**：使用队列存储每一层的节点，每次处理一层的所有节点 3. **方向控制**：通过布尔值 'isOrderLeft' 控制每层的遍历方向 - 当 'isOrderLeft' 为 true 时，从左到右遍历 - 当 'isOrderLeft' 为 false 时，从右到左遍历 4. **结果存储**：使用双端队列 'levelList' 存储当前层的节点值，根据遍历方向决定从队列的前端还是后端添加元素 5. **层切换**：完成一层遍历后，将当前层结果添加到最终结果中，并反转遍历方向 **关键步骤**： 1. 初始化队列，将根节点入队 2. 遍历队列，直到队列为空 3. 记录当前层的节点数量，遍历当前层的所有节点 4. 根据遍历方向，将节点值添加到双端队列的适当位置 5. 将当前节点的左右子节点入队 6. 完成当前层遍历后，将结果添加到最终列表，并反转遍历方向 7. 返回最终结果列表 **时间复杂度**：O(n)，其中 n 是二叉树的节点数。每个节点仅被访问一次。 **空间复杂度**：O(n)，需要使用队列存储节点，最坏情况下队列大小为树的最大宽度。