655. Print Binary Tree

# Medium

Key idea: compute the height of tree, build 2D array filled with "", then use recursive to fill root.val, from root to leaf

Python

# 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]]:
        h = self.height(root)
        res = []
        for i in range(h):
            res.append(["" for i in range((1<<h) - 1)])
        self.fill(res, root, 0, 0, len(res[0])-1)
        return res
        
    def fill(self, res, root, i, l, r):
        if root == None:
            return
        res[i][(l+r)//2] = str(root.val)
        self.fill(res, root.left, i+1, l, (l+r)//2-1)
        self.fill(res, root.right, i+1, (l+r)//2+1, r)
        
    def height(self, root):
        if root == None:
            return 0
        return max(self.height(root.left), self.height(root.right)) + 1

难点: recursive 中，fill左右两边时，不应该包括当前节点的那个index

Time = $O(h*2^h)$ , because of initilization, Space = $O(h*2^h)$