LeetCode 655. 输出二叉树

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
深度优先搜索 树 广度优先搜索 二叉树

题目描述

✅ 655. 输出二叉树

image-20260929104446844

image-20260929104446952

image-20260929104447046

题意分析

按题目规定将二叉树排入字符串矩阵：根在第一行中央，孩子在下一行对应的左右位置，未放节点的单元格保留空字符串。列宽由整棵树的高度决定，空子树对应的位置也必须保留。

解法：递归分配列区间

核心思路

[!blue]
先确定矩阵尺寸，再递归分配列区间。 代码中的 h 是层数：空树为 0，非空树为左右子树层数的较大值加一。它比题面按边数定义的高度多 1，因此输出应有 $h$ 行、$2^h-1$ 列。

这个列宽也可以从布局递推得到：一层只需一列，增加一层时，为左右子树各预留相同宽度，中间再留根的一列，所以 $W(h)=2W(h-1)+1=2^h-1$。即使某侧实际没有节点，也不能缩小它的预留区域，否则根和另一侧的位置都会偏移。

fill655(node, row, left, right) 表示把当前节点放到第 row 行、闭区间 [left, right] 的中央。先计算 mid 并写入节点值，再让左孩子负责下一行的 [left, mid - 1]，右孩子负责 [mid + 1, right]。两侧区间长度相同且互不重叠，因此所有节点的位置都由同一套完整布局确定。

当节点还有下一层可放时，左右半区中点与当前中点的距离恰好为 $2^{h-\mathrm{row}-2}$，与题面规定的孩子偏移一致。遇到空节点直接返回，预先填好的空字符串便自然保留下来。树的层数已经确定了行数，所以非空节点不会写到矩阵之外；一个节点的数值无论几位，都转换成字符串放入同一个单元格。

解题步骤

  1. 递归计算树的层数 h。
  2. 创建 h 行、2^h-1 列的空字符串矩阵。
  3. 从根开始，将节点值写入当前区间中点。
  4. 下一行分别处理左右半区，遇到空节点返回。

代码实现

class Solution {
    public List<List<String>> printTree(TreeNode root) {
        int h = height655(root);
        int w = (1 << h) - 1;

        List<List<String>> res = new ArrayList<>();

        for (int i = 0; i < h; i++) {
            List<String> row = new ArrayList<>();

            for (int j = 0; j < w; j++) {
                row.add("");
            }

            res.add(row);
        }

        fill655(root, 0, 0, w - 1, res);

        return res;
    }

    private int height655(TreeNode node) {
        if (node == null) {
            return 0;
        }

        return 1 + Math.max(height655(node.left), height655(node.right));
    }

    private void fill655(TreeNode node, int row, int left, int right, List<List<String>> res) {
        if (node == null || left > right) {
            return;
        }

        // 当前节点占区间中点，左右孩子分别使用下一行的两侧区间。
        int mid = (left + right) / 2;

        res.get(row).set(mid, String.valueOf(node.val));
        fill655(node.left, row + 1, left, mid - 1, res);
        fill655(node.right, row + 1, mid + 1, right, res);
    }
}

import "strconv"

func printTree(root *TreeNode) [][]string {
    h := height655(root)
    w := (1 << h) - 1

    res := make([][]string, h)
    for i := 0; i < h; i++ {
        res[i] = make([]string, w)
        for j := 0; j < w; j++ {
            res[i][j] = ""
        }
    }

    fill655(root, 0, 0, w-1, res)
    return res
}

func height655(node *TreeNode) int {
    if node == nil {
        return 0
    }
    lh := height655(node.Left)
    rh := height655(node.Right)
    if lh > rh {
        return lh + 1
    }
    return rh + 1
}

func fill655(node *TreeNode, row int, left int, right int, res [][]string) {
    if node == nil || left > right {
        return
    }
    // 当前节点占区间中点，左右孩子分别使用下一行的两侧区间。
    mid := (left + right) / 2
    res[row][mid] = strconv.Itoa(node.Val)
    fill655(node.Left, row+1, left, mid-1, res)
    fill655(node.Right, row+1, mid+1, right, res)
}

复杂度分析

  • 时间复杂度：$O(h2^h)$。求层数和填写节点各遍历一次树，初始化 $h(2^h-1)$ 个输出单元格占主导。
  • 空间复杂度：输出矩阵 $O(h2^h)$，递归辅助空间 $O(h)$。

关键点总结

[!green]

  • 层数与按边数定义的高度相差一，本实现使用层数。
  • 每个节点只填一个位置，其余位置保留空字符串。
  • 左右递归共用同一输出矩阵。
  • 只有根节点时 $h=1$，矩阵自然退化为一行一列，无需特殊分支。

易错点总结

[!yellow]

  • 混用两种高度定义：矩阵行数或列数会多一层。
  • 按实际节点数作为宽度：稀疏树仍需保留完整的分区空间。
  • 左右子树仍使用整个列区间：无法保持各自的位置范围。
  • 把空节点写成数字零：改变题目规定的输出内容。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/42948459
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！