输出二叉树

难度: Medium

给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：

树的高度为 height ，矩阵的行数 m 应该等于 height + 1 。
矩阵的列数 n 应该等于 2^height+1 - 1 。
根节点 需要放置在顶行的 正中间 ，对应位置为 res[0][(n-1)/2] 。
对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2^height-r-1] ，右子节点放置在 res[r+1][c+2^height-r-1] 。
继续这一过程，直到树中的所有节点都妥善放置。
任意空单元格都应该包含空字符串 "" 。

返回构造得到的矩阵 res 。

示例 1：

输入：root = [1,2]
输出：
[["","1",""],
 ["2","",""]]

示例 2：

输入：root = [1,2,3,null,4]
输出：
[["","","","1","","",""],
 ["","2","","","","3",""],
 ["","","4","","","",""]]

提示：

树中节点数在范围 [1, 2¹⁰] 内
-99 <= Node.val <= 99
树的深度在范围 [1, 10] 内

Submission

运行时间: 28 ms

内存: 15.9 MB

# 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 dfs(node: TreeNode) -> int:
            return max(dfs(node.left), dfs(node.right)) + 1 if node else 0
        
        def dfsTree(node: TreeNode, r: int, c: int):
            ans[r][c] = str(node.val)
            diff = 2 ** (height - 2 - r)
            if node.left:
                dfsTree(node.left, r + 1, c - diff)
            if node.right:
                dfsTree(node.right, r + 1, c + diff)
        
        height = dfs(root)
        ans = [[""] * (2 ** height - 1) for _ in range(height)]
        dfsTree(root, 0, (len(ans[0]) - 1) // 2)
        return ans

Explain

这个题解使用深度优先搜索(DFS)的方式遍历二叉树。首先通过一次 DFS 求出树的高度 height。然后创建大小为 height * (2^height - 1) 的答案矩阵，所有元素初始化为空字符串。接着从根节点开始进行另一次 DFS，在答案矩阵中填入对应节点的值。填入位置根据当前节点的高度以及是左子节点还是右子节点来确定。最后返回填好的答案矩阵即可。

时间复杂度: O(n)

空间复杂度: O(n)

# 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 dfs(node: TreeNode) -> int:
            return max(dfs(node.left), dfs(node.right)) + 1 if node else 0
        
        # 在答案矩阵中填入节点值
        def dfsTree(node: TreeNode, r: int, c: int):
            ans[r][c] = str(node.val)
            diff = 2 ** (height - 2 - r)  # 确定填入位置
            if node.left:  
                dfsTree(node.left, r + 1, c - diff) # 递归填左子树
            if node.right:
                dfsTree(node.right, r + 1, c + diff) # 递归填右子树
        
        height = dfs(root) # 求树高
        ans = [[""] * (2 ** height - 1) for _ in range(height)] # 构建答案矩阵
        dfsTree(root, 0, (len(ans[0]) - 1) // 2) # 从根节点开始填
        return ans

Explore

在计算左右子节点的位置时，`diff` 表示在填充答案矩阵中，子节点相对于父节点的水平偏移量。这个偏移量的计算方式`2 ** (height - 2 - r)`基于二叉树的层级结构和宽度。二叉树的每一层宽度大约是上一层的两倍，因此在第 `r` 层，从左到右的空间必须足够容纳所有可能的节点，即 `2 ** (height - r - 1)` 个潜在节点。而每个节点的左右子节点需要分别放在左半区和右半区的中心，故每个子节点与其父节点的距离为 `2 ** (height - r - 2)`。这里的 `-2` 是因为：要从这一层到下一层（减1），且下一层的宽度是这一层的一半（再减1）。

实际上，题解中并没有使用 `height - 1` 来初始化答案矩阵的行数，而是直接使用 `height`。代码中的 `ans = [[''] * (2 ** height - 1) for _ in range(height)]` 表示使用树的高度 `height` 作为行数。每一层的树对应答案矩阵的一行，因此需要的行数正好是二叉树的高度。

在填充答案矩阵时，通过精确计算每个节点值应该填充的位置，可以避免重复填充。具体地，每个节点的位置是根据其在树中的深度（行）和偏移量（列）计算得到的。由于二叉树的性质，每个节点最多有两个子节点，且每个子节点的位置都是基于父节点的位置进行偏移的。这种偏移方式保证了在树的不同层和不同分支中，每个节点的位置是唯一的，因此不会有两个节点填充在同一个位置。