题目描述
思路解析
一句话答案：LeetCode 655 输出二叉树：因为矩阵尺寸完全由树能长多深决定，先量树高定下行数和列数，再用 DFS 把每个节点放到它那行、那段区间的正中，空格填空串，时间 O(m·n)。
把一棵二叉树摆进一张 m×n 的字符串矩阵
给一棵二叉树的根 root，要把它画进一张 m 行 n 列的字符串矩阵。行数 m 是树高 height 加一，列数 n 是 2^(height+1) − 1，根写在顶行正中，每个节点的左右孩子落到下一行、往两侧偏开一段，空格填空串。题面 root=[1,2] 输出 [["","1",""],["2","",""]]，高 1、2 行 3 列。
矩阵开多大、每个数落哪一格，都得先算准
难点不在遍历，在两处定位。矩阵多大，取决于树往下长多深：树高多一层，行数多一行、列数翻倍再减一。节点落哪一列，取决于它在第几层、从父节点哪侧分下来。任一处算偏，数就摆错格甚至越界。
尺寸由树高定，每往下一层偏移就对半缩
先求树高 h，也就是从根到最远叶子要走的边数。约定空节点高度是 −1，只有一个节点的树高度恰好是 0。有了 h,m = h+1 行、n = 2^(h+1) − 1 列。安放靠一次 DFS，顺着一条枝走到底再回头。DFS 到每个节点，带着行号 r、列号 c，把值写进 res[r][c]，再把 c 减、加偏移量传给左右孩子。偏移量是 2^(h−r−1)，根在第 0 层最大，越往下每层对半缩，因为越深的节点能占的列区间越窄。
DFS 在每格写一个值，再把区间对半分给左右孩子
从根开始 dfs(root, 0, (n−1)/2)：根站顶行正中。到节点 res[r][c] 先填值，再算偏移 d = 2^(h−r−1)，左孩子去 res[r+1][c−d]、右孩子去 res[r+1][c+d]，各自站到下一行那半区间的正中。碰到空节点直接返回，那格保持空串。整条递归只在重复一个动作：站中点、把区间对半分往下带。
拿 root=[1,2,3,null,4] 亲手摆一遍
先量高。叶子 3、4 高度都是 0;节点 2 挂着 4，高度 1;根 1 取较大的加一得高度 2,h=2。尺寸定下：m = 2+1 = 3 行，n = 2^3 − 1 = 7 列。根列 = (7−1)/2 = 3，把 1 写进 res[0][3]。
根在第 0 层，偏移 d = 2^(2−0−1) = 2：左孩子 2 落到 res[1][3−2]=res[1][1]，右孩子 3 落到 res[1][5]。节点 2 在第 1 层，偏移缩成 d = 2^(2−1−1) = 1，它没有左孩子，右孩子 4 落到 res[2][2]。4 正落在 res[2][2]，与题面一致。
空节点高度、列数、偏移，三处约定别记混
空节点高度得记 −1 而不是 0——记成 0，树高虚高一层、行列一起多算。列数是 2^(h+1) − 1 而非 2^h，少写那一倍宽度，右边节点就越界或叠到一起。偏移量随层递减 2^(h−r−1)，写成固定值，深层节点全站错列。空格填的是空串，既非 null 也非空格。
矩阵有 h+1 行、2^(h+1) − 1 列，光建表填空串就是 O(m·n);DFS 每个节点只走一次，递归栈最深到树高 O(h)，被矩阵盖过，时间空间都是 O(m·n)。单节点是 1×1 矩阵，root=[1,2] 则是 2 行 3 列、根居中孩子落在半边角上。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「占区间、站中点、左右对半分」这句口诀,下面每一帧都在套它。
输入 · 这棵树：这就是要画的树:根是 50,左孩子 30、右孩子 80;30 底下还挂着 10,80 底下挂着 90。一共 5 个节点,我们要把它们摆进矩阵。
第一步 · 量树高 h：先量树高。从根一路往下数最长的那条路,50 到 30 再到 10,走了两条边,所以树高 h 等于 2。约定空节点高度是 −1,这样叶子的高度刚好是 0。
第一步 · 定矩阵大小：有了 h,矩阵尺寸就定了。行数 m 等于 h 加 1,也就是 3 行;列数 n 等于 2 的 (h+1) 次方再减 1,等于 2 的 3 次方减 1,也就是 7 列。接下来就在这张 3 行 7 列的网格上摆数。
建空矩阵：先把这张 3 行 7 列的矩阵全部填上空串,得到一张干净的网格。现在从根开始,做一次 DFS 把节点一个个放进去。
放 50 · 算中点：轮到节点 50。它分到的列区间是 [0, 6](蓝色高亮这一段),中点等于 (0+6) 除以 2,也就是第 3 列。50 就站在这一格的正中间。
放 50 · 落格：把 50 写进 res[0][3],这一格点亮。它还有孩子,接着要把区间对半分给左右子树。
50 · 对半分区间：50 把自己的区间从中点劈开:左半段 [0, 2] 留给左孩子,右半段 [4, 6] 留给右孩子。两个孩子都掉到下一行,各自再去站自己那半段的中点。
放 30 · 算中点：轮到节点 30。它分到的列区间是 [0, 2](蓝色高亮这一段),中点等于 (0+2) 除以 2,也就是第 1 列。30 就站在这一格的正中间。
放 30 · 落格：把 30 写进 res[1][1],这一格点亮。它还有孩子,接着要把区间对半分给左右子树。
30 · 对半分区间：30 把自己的区间从中点劈开:左半段 [0, 0] 留给左孩子,右半段 [2, 2] 留给右孩子。两个孩子都掉到下一行,各自再去站自己那半段的中点。
放 10 · 算中点：轮到节点 10。它分到的列区间是 [0, 0](蓝色高亮这一段),中点等于 (0+0) 除以 2,也就是第 0 列。10 就站在这一格的正中间。
放 10 · 落格：把 10 写进 res[2][0],这一格点亮。它是叶子,没有孩子,这条分支到底了。
30 · 右孩子为空：30 没有右孩子,右半段 [2, 2] 也就空着。可以看到这些空格正好对应树上缺失的子树位置。
放 80 · 算中点：轮到节点 80。它分到的列区间是 [4, 6](蓝色高亮这一段),中点等于 (4+6) 除以 2,也就是第 5 列。80 就站在这一格的正中间。
放 80 · 落格：把 80 写进 res[1][5],这一格点亮。它还有孩子,接着要把区间对半分给左右子树。
80 · 对半分区间：80 把自己的区间从中点劈开:左半段 [4, 4] 留给左孩子,右半段 [6, 6] 留给右孩子。两个孩子都掉到下一行,各自再去站自己那半段的中点。
80 · 左孩子为空：80 没有左孩子,所以左半段 [4, 4] 不放任何值,整段一直是空串。空的地方就是树里缺的那条枝。
放 90 · 算中点：轮到节点 90。它分到的列区间是 [6, 6](蓝色高亮这一段),中点等于 (6+6) 除以 2,也就是第 6 列。90 就站在这一格的正中间。
放 90 · 落格：把 90 写进 res[2][6],这一格点亮。它是叶子,没有孩子,这条分支到底了。
放置完成：五个节点全部放完。每个值都站在自己区间的正中央,空格保持空串。这张矩阵就是树的格式化布局,从上往下、左右对称地排开。
对照样例：对照一下:第 0 行正中间是 50,第 1 行 30 和 80 对称地分在左右,第 2 行最外侧是 10 和 90。每一格都和正确答案对得上,DFS 区间取中点的办法奏效。
边界先想清:单节点就是 1×1 矩阵;只有两个节点时是 2 行 3 列,根居中、孩子落在对应那半边的角上。
面试重点:讲清偏移量为什么随层减半,以及 DFS 怎么把行列坐标顺着递归带下去。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def printTree(self, root: Optional[TreeNode]) -> List[List[str]]: def height(root): if root is None: return -1 return 1 + max(height(root.left), height(root.right)) def dfs(root, r, c): if root is None: return ans[r][c] = str(root.val) dfs(root.left, r + 1, c - 2 ** (h - r - 1)) dfs(root.right, r + 1, c + 2 ** (h - r - 1)) h = height(root) m, n = h + 1, 2 ** (h + 1) - 1 ans = [[""] * n for _ in range(m)] dfs(root, 0, (n - 1) // 2) return ans复杂度
- 时间：O(m × n)，矩阵有 m=(h+1) 行、n=2^(h+1)−1 列,建表与填空串就要 O(m·n);DFS 只访问每个节点一次,被填表开销盖过
- 空间：O(m × n)，结果矩阵本身占 O(m·n);递归栈深度是树高 O(h),相比矩阵更小
易错点
面试追问把动画讲成自己的话
追问为什么偏移量是 2^(h−r−1),会随层减半?
追问用 DFS 还是 BFS 都行吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长同值路径
LeetCode 687 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题