LeetCode 剑指 Offer 32 - III. 从上到下打印二叉树 III

Categories:

题目描述
思路分析
1. 解法一：层序遍历 + 双向填充（推荐）
相似题目

题目描述

✅ 剑指 Offer 32 - III. 从上到下打印二叉树 III

思路分析

解法一：层序遍历 + 双向填充（推荐）

核心思路：

采用 BFS 按层遍历二叉树。

偶数层从左到右、奇数层从右到左，使用数组按索引填充。

每层遍历后切换方向。

复杂度分析：

时间复杂度：O(n)，其中 n 为结点数量。

空间复杂度：O(n)，队列占用。

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

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

        // BFS 分层遍历并按方向填充
        while (!queue.isEmpty()) {
            int size = queue.size();
            Integer[] level = new Integer[size];
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                int idx = leftToRight ? i : size - 1 - i;
                level[idx] = node.val;

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

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

        return ans;
    }
}

func levelOrder(root *TreeNode) [][]int {
    ans := make([][]int, 0)
    if root == nil {
        return ans
    }

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

    // BFS 分层遍历并按方向填充
    for len(queue) > 0 {
        size := len(queue)
        level := make([]int, size)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            idx := i
            if !leftToRight {
                idx = size - 1 - i
            }
            level[idx] = node.Val

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

    return ans
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS
103. 二叉树的锯齿形层序遍历	中等	BFS
107. 二叉树的层序遍历 II	中等	BFS
199. 二叉树的右视图	中等	BFS
429. N 叉树的层序遍历	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/82368797