655. 输出二叉树

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/print-binary-tree/
Star
在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
  1. 行数 m 应当等于给定二叉树的高度。
  1. 列数 n 应当总是奇数。
  1. 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
  1. 每个未使用的空间应包含一个空的字符串""。
  1. 使用相同的规则输出子树。
示例 1:
输入:
     1
    /
   2
输出:
[["", "1", ""],
 ["2", "", ""]]
示例 2:
输入:
     1
    / \
   2   3
    \
     4
输出:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]
示例 3:
输入:
      1
     / \
    2   5
   /
  3
 /
4
输出:
[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]
注意: 二叉树的高度在范围 [1, 10] 中。

法1

思路
输出的结果为二维数组，数组大小为 h * w 其中h为二叉树的高度，w二叉树的宽度 w = 2 ** h - 1
所以先构建出空的数组，再去填充节点的值。具体填充的时候，需要用到当前节点的高度，即数组的横坐标，当前节点需要的位置，有left和right决定
题解
# 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: TreeNode) -> List[List[str]]:
        # 计算二叉树高度，并定义空的 rsult
        h = self.getHight(root)
        w = 2**h - 1
        res = [["" for _ in range(w)] for _ in range(h)]
        # 填充result
        self.fill(node=root, result=res, depth=0, left=0, right=w-1)
        return res
    
    def fill(self, node, result, depth, left, right):
        '''
        node : 填充的当前节点
        result: 最终的结果
        depth:当前节点的深度
        left right:在result中填充的位置 是left 和rigth 的中间位置

        '''
        if node is None:
            return
        result[depth][left+(right-left)//2] = str(node.val)
        self.fill(node.left, result, depth+1, left, left+(right-left)//2)
        self.fill(node.right, result, depth+1, left+(right-left)//2 + 1, right)
    
    def getHight(self, node):
        if node is None:
            return 0
        return max(self.getHight(node.left), self.getHight(node.right)) + 1