이진 트리 인쇄

이진 트리의 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:



입력: 루트 = [1,2]
산출:
[["","1",""],
["2","",""]]

예 2:



입력: 루트 = [1,2,3,null,4]
산출:
[["","","","1","","",""],
["","2","","","","3",""],
["","","4","","","",""]]

제약:

트리의 노드 수가 [1, 210] 범위에 있습니다.

-99 <= Node.val <= 99

트리의 깊이는 [1, 10] 범위에 있습니다.

해결책:

# 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 getHeight(self, root):
        if root:
            return 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        return 0

    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        h = self.getHeight(root)
        cols = (1 << h) - 1
        rows = h
        op = [["" for i in range(cols)] for j in range(rows)]
        nodes = [(root, 0, 0, cols)]
        while len(nodes) > 0:
            curr, l, a, b = nodes.pop()
            if curr:
                i = (a + b) // 2
                op[l][i] = str(curr.val)
                nodes.append((curr.left, l + 1, a, i))
                nodes.append((curr.right, l + 1, i, b))
        return op