LeetCode 题解工作台
输出二叉树
给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则： 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。 矩阵的列数 n 应该等于 2 heig…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
先通过 `DFS` 求二叉树的高度 （高度从 `0` 开始），然后根据 求得结果列表的行数 和列数 。 根据 , 初始化结果列表 `ans`，然后 `DFS` 遍历二叉树，依次在每个位置填入二叉树节点值（字符串形式）即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：
- 树的 高度 为
height，矩阵的行数m应该等于height + 1。 - 矩阵的列数
n应该等于2height+1 - 1。 - 根节点 需要放置在 顶行 的 正中间 ，对应位置为
res[0][(n-1)/2]。 - 对于放置在矩阵中的每个节点，设对应位置为
res[r][c]，将其左子节点放置在res[r+1][c-2height-r-1]，右子节点放置在res[r+1][c+2height-r-1]。 - 继续这一过程，直到树中的所有节点都妥善放置。
- 任意空单元格都应该包含空字符串
""。
返回构造得到的矩阵 res 。
示例 1：
输入：root = [1,2] 输出： [["","1",""], ["2","",""]]
示例 2：
输入：root = [1,2,3,null,4] 输出： [["","","","1","","",""], ["","2","","","","3",""], ["","","4","","","",""]]
提示：
- 树中节点数在范围
[1, 210]内 -99 <= Node.val <= 99- 树的深度在范围
[1, 10]内
解题思路
方法一：两次 DFS
先通过 DFS 求二叉树的高度 （高度从 0 开始），然后根据 求得结果列表的行数 和列数 。
根据 , 初始化结果列表 ans，然后 DFS 遍历二叉树，依次在每个位置填入二叉树节点值（字符串形式）即可。
时间复杂度 ，空间复杂度 。其中 是二叉树的高度。忽略结果返回值的空间消耗。
# 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 = right
class 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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for traversing all n nodes of the tree. Space complexity is O(n) for storing the resulting matrix and O(h) for the recursion stack, where h is the tree height. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may emphasize correct node placement for symmetric visualization.
- question_mark
Expect discussion of DFS versus BFS for position calculation.
- question_mark
Watch for questions about handling null children and empty cells.
常见陷阱
外企场景- error
Miscalculating column mid-points causing misaligned nodes.
- error
Not initializing the matrix to correct dimensions before filling values.
- error
Confusing depth and height, leading to incorrect row or column counts.
进阶变体
外企场景- arrow_right_alt
Output tree nodes level by level but preserve relative horizontal spacing for symmetry.
- arrow_right_alt
Print only the left or right subtree matrix while maintaining column alignment.
- arrow_right_alt
Adapt to non-binary trees, adjusting column calculation for multiple children per node.