655. 输出二叉树(中)

• 题目
• 题解

题目

• 给你一棵二叉树的根节点 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 。

题解

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)#左子结点列相较于中间向左偏移diff
            # 处理右子节点
            if node.right:
                dfsTree(node.right, r + 1, c + diff)#右子结点列相较于中间向右偏移diff
        # 计算树的高度
        height = dfs(root)
        # 初始化二维列表，用于存储节点值
        ans = [[""] * (2 ** height - 1) for _ in range(height)]  
        # 执行深度优先搜索，并填充二维列表
        dfsTree(root, 0, (len(ans[0]) - 1) // 2) #传入根节点、行号、中间列的索引
        # 返回填充好的二维列表
        return ans