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

Categories:

Tags:

题目描述
思路分析
1. 解法一：BFS（按层填充）（推荐）
2. 解法二：DFS（按层插入）
相似题目

题目描述

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

题目：

给定二叉树的根节点 root，返回其节点值的锯齿形层序遍历结果，即各层交替从左到右、从右到左进行遍历。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目范围是 [0, 2000]
-100 <= Node.val <= 100

思路分析

解法一：BFS（按层填充）（推荐）

核心思路：

使用队列进行层序遍历。

通过一个布尔变量 leftToRight 控制当前层的填充方向。

对每层预分配数组，按方向决定写入位置：i 或 size-1-i。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树节点数。

空间复杂度：O(n)，其中 n 表示队列最宽层节点数。

// BFS 按方向填充
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        boolean leftToRight = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            Integer[] level = new Integer[size];

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                int index = leftToRight ? i : size - 1 - i;
                level[index] = node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            res.add(Arrays.asList(level));
            leftToRight = !leftToRight;
        }

        return res;
    }
}

// BFS 按方向填充
func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}

	var res [][]int
	queue := []*TreeNode{root}
	leftToRight := true

	for len(queue) > 0 {
		size := len(queue)
		level := make([]int, size)

		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			index := i
			if !leftToRight {
				index = size - 1 - i
			}
			level[index] = node.Val

			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		res = append(res, level)
		leftToRight = !leftToRight
	}

	return res
}

解法二：DFS（按层插入）

核心思路：

递归遍历时携带 depth。

当 depth 为偶数时尾插，奇数时头插，形成锯齿顺序。

需要确保每层列表已初始化。

复杂度分析：

时间复杂度：O(n)，其中 n 表示二叉树节点数。

空间复杂度：O(n)，其中 n 表示递归栈深度与结果集合规模。

// DFS 按层插入
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }

    private void dfs(TreeNode node, int depth, List<List<Integer>> res) {
        if (node == null) {
            return;
        }

        if (depth == res.size()) {
            res.add(new ArrayList<>());
        }

        if (depth % 2 == 0) {
            res.get(depth).add(node.val);
        } else {
            res.get(depth).add(0, node.val);
        }

        dfs(node.left, depth + 1, res);
        dfs(node.right, depth + 1, res);
    }
}

// DFS 按层插入
func zigzagLevelOrder(root *TreeNode) [][]int {
	var res [][]int
	dfsZigzag(root, 0, &res)
	return res
}

func dfsZigzag(node *TreeNode, depth int, res *[][]int) {
	if node == nil {
		return
	}

	if depth == len(*res) {
		*res = append(*res, []int{})
	}

	if depth%2 == 0 {
		(*res)[depth] = append((*res)[depth], node.Val)
	} else {
		level := (*res)[depth]
		level = append([]int{node.Val}, level...)
		(*res)[depth] = level
	}

	dfsZigzag(node.Left, depth+1, res)
	dfsZigzag(node.Right, depth+1, res)
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS
3417. 跳过交替单元格的之字形遍历	简单	模拟、之字形遍历
107. 二叉树的层序遍历 II	中等	BFS
199. 二叉树的右视图	中等	BFS、DFS
637. 二叉树的层平均值	简单	BFS
429. N 叉树的层序遍历	中等	BFS
515. 在每个树行中找最大值	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/76709919