LeetCode 655. 输出二叉树

2023-05-03 HGNULB 约 9 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 655. 输出二叉树

题意分析

要什么：把一棵二叉树画进一个字符串矩阵：矩阵的行数等于树的高度 h，列数等于 $2^h - 1$；根放在第 0 行的正中间；某个节点若落在第 r 行的第 c 列，它的左孩子落在第 r+1 行、左半区的正中间，右孩子落在第 r+1 行、右半区的正中间；其余格子填空字符串。
约束透露的信号：矩阵尺寸由树高唯一决定，而树高必须先算出来才能开数组——这就注定了两趟结构：先求高度定尺寸，再填内容。列数是 $2^h - 1$ 这个数字本身也在提示答案：宽度为 $2^h - 1$ 的区间，中点左右各剩 $2^{h-1} - 1$ 格，恰好又是下一层所需的宽度，递归天然对齐、永不越界。节点数上限只有几百，说明矩阵规模可控，可以放心地按 $2^h$ 开空间。
边界：空树在本题的约束下不会出现（至少有根节点），但高度函数仍要处理空指针；只有一个节点时 h = 1、w = 1，矩阵是 [["1"]]；节点值需要转成字符串填入，不能直接放整数；「区间为空」和「节点为空」是两个不同的终止条件，虽然本题中前者不会先于后者发生，写上更安全。

解法：先求高度，再递归填充区间

核心思路

第一反应可能是层序遍历：一层层往下走，每层算出每个节点该放在哪一列。可行，但每层都要重新推导列的位置，还得同时跟踪「这个节点属于哪个父区间」，状态很容易乱。
换个角度看这张图：每个节点其实拥有一段横向区间，它自己占据区间的中点，左右孩子分别继承左右两个子区间。这个描述是自顶向下、递归自洽的，比按层推导简单得多。
于是把问题拆成两问。第一问「矩阵该多大」：行数就是树高，列数是 $2^h - 1$，都由高度决定，所以先做一次常规的求高度递归。第二问「每个节点填在哪」：定义递归 fill(node, row, left, right)，其不变量是——节点 node 必须被画在第 row 行、列区间 [left, right] 的正中间，且它的整棵子树都只会画在这个区间之内。
这条不变量为什么闭合？初始调用是 fill(root, 0, 0, w-1)，区间宽度 $2^h - 1$，中点为 mid。左边剩下 [left, mid-1]，宽度恰是 $2^{h-1} - 1$，正好等于「高度为 h-1 的子树」所需的宽度；右边同理。所以只要初始宽度取对，每一层的区间宽度都会自动匹配该层子树的需要，既不会越界也不会重叠——这就是题目把列数定成 $2^h - 1$ 的原因。
空节点直接返回，对应的整片区间保持初始的空字符串，不需要显式清理。

解题步骤

先递归求树高：空节点返回 0，否则返回 1 + max(左高, 右高)。为什么必须先求高度：矩阵的行数和列数都依赖 h，而 h 只有遍历完整棵树才能确定，无法边填边扩。

按 h 行、$2^h - 1$ 列建矩阵，所有格子预填空字符串。为什么用 1 << h 计算宽度：位移比 Math.pow 快且返回整数，避免浮点误差；h 不超过十几，不会溢出。为什么预填空串而不是 null：题目要求空位是空字符串，Java 的 ArrayList 不预填就没有对应下标可 set，Go 的切片零值恰好是空串但显式写出更清楚。

从 fill(root, 0, 0, w - 1) 开始递归。为什么右边界是 w - 1：区间用闭区间表示，最后一列的下标是 w - 1；写成 w 会让中点整体右偏并在最深层越界。

递归体中先处理终止条件：节点为空或区间为空则直接返回。为什么两个条件都要：节点为空说明这棵子树不存在，整片区间留白；区间为空是防御性判断，一旦高度或宽度算错能提前止损而不是越界崩溃。

计算 mid = (left + right) / 2，把节点值转成字符串写进 res[row][mid]。为什么取中点：题目规定节点画在其区间正中；由于宽度恒为奇数（$2^k - 1$ 形式），中点唯一且左右子区间长度严格相等。

递归左孩子到 (row + 1, left, mid - 1)、右孩子到 (row + 1, mid + 1, right)。为什么左右都要排除 mid 本身：mid 已经被当前节点占用，孩子若能落在这一列就会覆盖父节点。

以 root = [1, 2]（根为 1，左孩子为 2，无右孩子）走一遍。求高度：右子树高 0、左子树高 1，故 h = 2，宽度 w = 2^2 - 1 = 3，先建成 2 行 3 列的全空矩阵。调用 fill(节点1, row=0, left=0, right=2)：mid = (0 + 2) / 2 = 1，于是 res[0][1] = "1"。递归左孩子 fill(节点2, row=1, left=0, right=0)：mid = 0，于是 res[1][0] = "2"；它再往下递归时节点为空，立即返回。递归右孩子 fill(null, row=1, left=2, right=2)：节点为空直接返回，res[1][2] 保持空串。最终矩阵是 [["", "1", ""], ["2", "", ""]]，与期望输出一致——注意第 1 行只在最左列有值，因为节点 2 的可用区间被父节点切成了 [0, 0]。

代码实现

// 核心实现：先求高度，再递归填充区间，维护必要状态并避免重复处理。
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);
    }
}

// 核心实现：先求高度，再递归填充区间，维护必要状态并避免重复处理。
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(h \cdot 2^h)$。凭什么：初始化矩阵要写满 $h \times (2^h - 1)$ 个格子，这是主项；填充递归只访问 n 个真实节点、每个节点做常数工作，而 n 不超过 $2^h - 1$，被主项吸收。

空间复杂度：$O(h \cdot 2^h)$。凭什么：输出矩阵本身就占这么多；除此之外只有深度为 h 的递归栈，量级远小。

关键点总结

尺寸依赖全局信息时，就老老实实分两趟：一趟求出决定容器大小的量（这里是树高），一趟填内容。想把两件事挤进一次遍历，往往要靠动态扩容或回填，得不偿失。

「节点占据一段区间、孩子继承左右半区」是区间递归的经典范式，比按层推坐标更容易写对。同类思路可以迁移到把有序数组转成平衡 BST、线段树建树等场景。

$2^h - 1$ 这个宽度不是随便定的：它保证每次去掉中点后两个半区的宽度仍是 $2^{h-1} - 1$，递归自然对齐。理解这一点，就不必在每层手算坐标偏移。

递归函数的参数就是它的契约。本题的契约是「你负责把这棵子树画在第 row 行的 [left, right] 区间里」，只要每次调用都满足这个契约，正确性就是显然的。面试里把契约先说清楚，代码会写得又快又稳。

面试视角：先问清楚「空位填什么」「节点值是数字还是字符串」这两个输出格式问题，再动手；这类偏实现的题失分点几乎都在格式而非算法。

易错点总结

错误写法：把宽度算成 $2^h$ 或 $2^{h-1} - 1$；用例单节点树 → 前者得到宽度 2、中点为 1，输出 [["", "1"]] 与期望的 [["1"]] 不符；后者得到宽度 0，矩阵为空直接崩溃。

错误写法：初始调用写成 fill(root, 0, 0, w)；用例 root = [1, 2] → mid = (0 + 3) / 2 = 1 尚可，但递归到右半区 [2, 3] 时会访问下标 3，数组越界。

错误写法：递归孩子时区间写成 [left, mid] 和 [mid, right]；用例 root = [1, 2, 3] → 孩子的中点可能落回 mid，把父节点的值覆盖掉，输出中根节点消失。

错误写法：高度函数对空节点返回 1；用例单节点树 → 算出 h = 2、宽度 3，输出多了一整行空行，行数与期望不符。

错误写法：先填矩阵再算高度，或者边递归边动态扩容；用例任意树 → 填充时矩阵尚不存在或行数不足，抛出下标越界。

错误写法：把节点值直接放进 List<Integer> 或忘记转字符串；用例 root = [1] → 返回类型与题目要求的 List<List<String>> 不匹配，编译失败或输出格式判错。

错误写法：空位填 null 或 " "（一个空格）；用例 root = [1, 2] → 期望空位是长度为 0 的空串，填空格会导致逐元素比较失败。

错误写法：递归终止只判断 left > right 而不判断节点为空；用例任意含空孩子的树 → 对 null 节点访问 .val 直接空指针异常。

错误写法：改用层序遍历但按「第 k 层第 i 个位置」直接算列号，忽略了缺失节点会让同层节点错位；用例 root = [1, 2, null, 3] → 节点 3 被算到错误的列上，整棵左子树的画法偏移。

错误写法：mid 用 (left + right + 1) / 2 向上取整；用例 root = [1, 2] → 根被画到列 1 尚可，但左子区间变成 [0, 0] 之外的错误范围，深层节点位置整体右偏，与期望矩阵不一致。

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	只需本题的第一趟，是「先求高度」这一步的独立练习
102. 二叉树的层序遍历	中等	同样按层组织输出，但不需要列坐标，缺失节点直接跳过而非留白
297. 二叉树的序列化与反序列化	困难	也要为空节点保留占位，但目标是可逆编码而不是可视化排版