LeetCode 655 题详解：二叉树的二维数组格式化打印-java教程-PHP中文网

LeetCode 655 题详解：二叉树的二维数组格式化打印

本文详解如何将二叉树按规则渲染为 m×n 的二维字符串数组，要求行数等于树高、列数为奇数、根居中、左右子树对称留白，并给出完整 java 实现与关键逻辑解析。

本文详解如何将二叉树按规则渲染为 m×n 的二维字符串数组，要求行数等于树高、列数为奇数、根居中、左右子树对称留白，并给出完整 java 实现与关键逻辑解析。

在 LeetCode 第 655 题 Print Binary Tree 中，我们需要将一棵二叉树以结构化、可视化、可对齐的方式输出为二维字符串数组（List>），而非简单递归打印或缩进式文本。该题不仅考察树的遍历能力，更强调空间建模与分治思维——核心在于：如何为每层节点精准分配列位置，并保证左右子树占据对称且等宽的子区域。

✅ 解题三步法

1. 确定二维数组尺寸

行数 m = 树的高度（从根到最深叶节点的边数，或节点数；本题采用「节点层数」定义，即 height(root) = 1 + max(height(left), height(right))，空树高度为 0）。
列数 n = 2^h − 1（h 为树高），这是满二叉树最底层的最大节点数，且恒为奇数，满足题目约束。

private int getHeight(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}

2. 构建结果容器

初始化 m × n 的二维列表，全部填充空字符串 ""：

fill(res, node, row, left, right)

row：当前节点应填入的行索引；
[left, right]：当前子树在该行可用的列区间闭区间；
列中心 mid = left + (right - left) / 2 即为当前节点位置；
左子树递归区间 [left, mid-1]，右子树递归 [mid+1, right]，行号 +1。

private void fill(String[][] res, TreeNode node, int row, int left, int right) {
    if (node == null) return;
    int mid = left + (right - left) / 2;
    res[row][mid] = String.valueOf(node.val);
    fill(res, node.left,  row + 1, left,   mid - 1);
    fill(res, node.right, row + 1, mid + 1, right);
}

调用入口：fill(res, root, 0, 0, width - 1);

? 完整可运行示例（Java）

import java.util.*;

public class Solution {
    public List<list>> printTree(TreeNode root) {
        int h = getHeight(root);
        int width = (1 > res = new ArrayList();
        for (String[] row : grid) {
            res.add(Arrays.asList(row));
        }
        return res;
    }

    private int getHeight(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(getHeight(root.left), getHeight(root.right));
    }

    private void fill(String[][] grid, TreeNode node, int row, int left, int right) {
        if (node == null) return;
        int mid = left + (right - left) / 2;
        grid[row][mid] = String.valueOf(node.val);
        fill(grid, node.left,  row + 1, left,   mid - 1);
        fill(grid, node.right, row + 1, mid + 1, right);
    }
}</list>

⚠️ 注意事项与常见误区

❌ 不要用 StringBuilder 拼接缩进：本题要求严格二维坐标对齐，非文本缩进渲染；
❌ 避免列宽计算错误：n = 2^h − 1 是充要条件，不可用 2 * maxChildWidth + 1 迭代计算（易错且低效）；
✅ 空节点不占位但留白：null 子树不写入值，但其对应子区间仍被保留，确保左右对称；
✅ 边界安全：left > right 时直接返回，防止数组越界；
? 调试建议：对示例 1 / \ 2 3 \ 4，手动验证 h=3 → width=7，根在 (0,3)，左子在 (1,1)，右子在 (1,5)，4 在 (2,2)，完全匹配题干输出。