题目描述
思路解析动画文字版
记住「占区间、站中点、左右对半分」这句口诀,下面每一帧都在套它。
输入 · 这棵树：这就是要画的树:根是 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题