题目

655. 输出二叉树

给你一棵二叉树的根节点 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","",""]]
1
2
3
4

示例 2：

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

提示：

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

题解1

思路

• 先获取树的高度，然后据此初始化结果矩阵
• 每一次讲矩阵中央填为根节点的值，然后分别递归矩阵左右两侧
• 

代码

# 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 depth(node: Optional[TreeNode]):
            if not node: return 0
            return max(depth(node.left), depth(node.right))+1
        height = depth(root)-1
        ret = [[""]*(2**(height+1)-1) for _ in range(height+1)]
        def recur(node: Optional[TreeNode], r1:int, c1: int, r2: int, c2: int):
            if not node: return
            ret[r1][(c1+c2)//2] = str(node.val)
            recur(node.left, r1+1,c1,r2,(c1+c2)//2-1)
            recur(node.right, r1+1,(c1+c2)//2+1,r2,c2)
        recur(root, 0,0, len(ret), len(ret[0]))
        return ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(height)$

题解2

思路

• 先获取树的高度，然后据此初始化结果矩阵
• dfs遍历所有结点，其中根节点的位置为$res[0][\frac{n-1}{2}]$，左子树的节点位置为$res[r+1][c-2^{height-r-1}]$，右子树的节点位置为$res[r+1][c+2^{height-r-1}]$

代码

# 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 depth(node: Optional[TreeNode]):
            return max(depth(node.left), depth(node.right))+1 if node else 0
        height = depth(root)-1
        ret = [[""]*(2**(height+1)-1) for _ in range(height+1)]
        def dfs(node: Optional[TreeNode], r: int, c: int):
            if not node: return
            ret[r][c] = str(node.val)
            dfs(node.left, r+1, c-2**(height-r-1))
            dfs(node.right, r+1, c+2**(height-r-1))
        dfs(root, 0, (2**(height+1)-2)//2)
        return ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(height)$

题解3

思路

• 先获取树的高度，然后据此初始化结果矩阵
• Bfs遍历所有结点，其中根节点的位置为$res[0][\frac{n-1}{2}]$，左子树的节点位置为$res[r+1][c-2^{height-r-1}]$，右子树的节点位置为$res[r+1][c+2^{height-r-1}]$

代码

# 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 depth(node: Optional[TreeNode]):
            return max(depth(node.left), depth(node.right))+1 if node else 0
        height = depth(root)-1
        ret = [[""]*(2**(height+1)-1) for _ in range(height+1)]
        queue = collections.deque([(root, 0, (2**(height+1)-2)//2)])
        while queue:
            node, r, c = queue.popleft()
            ret[r][c] = str(node.val)
            if node.left: queue.append((node.left, r+1, c-2**(height-r-1)))
            if node.right: queue.append((node.right, r+1, c+2**(height-r-1)))
        return ret
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(2^{height})$