Print Binary Tree

Problem Id: 655 Difficulty: Medium Tag: Tree


Intuition

First we need to get the height of this binary tree height. Then, the width of the print board would be 2 ^ height - 1 * height. And the shift of each node would be 2 ** (height - depth - 2).

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def printTree(self, root: TreeNode) -> List[List[str]]:
        height = self._depth(root)
        width = 2 ** height - 1
        shift = 2 ** (height - 2)
        print_board = [[""] * width for _ in range(height)]
        self._print(root, width // 2, shift, 0, print_board)
        return print_board

    def _depth(self, node):
        if node is None:
            return 0
        return max(self._depth(node.left), self._depth(node.right)) + 1

    def _print(self, node, pos, shift, depth, print_board):
        if node is None:
            return
        print_board[depth][pos] = str(node.val)
        self._print(node.left, pos - shift, shift // 2, depth + 1, print_board)
        self._print(node.right, pos + shift, shift // 2, depth + 1, print_board)