Leetcode 655 Solution

This article provides solution to leetcode question 655 (print-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 655" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/print-binary-tree

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]]:
        self.widths = [0] * 10
        self.height = 0

        def get_width(node, depth):
            if node is None:
                return 0
            left_width = get_width(node.left, depth + 1)
            right_width = get_width(node.right, depth + 1)
            width = 1 + 2 * max(left_width, right_width)
            self.widths[depth] = max(self.widths[depth], width)
            self.height = max(self.height, depth)
            return width

        get_width(root, 0)

        self.ans = [[""] * self.widths[0] for _ in range(self.height + 1)]

        def fill(node, depth, offset):
            if node is None:
                return

            mid = self.widths[depth] // 2
            self.ans[depth][offset + mid] = str(node.val)

            fill(node.left, depth + 1, offset)
            fill(node.right, depth + 1, offset + mid + 1)

        fill(root, 0, 0)

        return self.ans