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