Simple Python - Binary partitions O(n)


  • 0
    E

    We can determine the width of the print result by applying this formula: # of max nodes in the maximum depth + cumulative sum of nodes from levels before. This essentially then becomes 2 ** max_depth - 1 due to the nature of binary trees. After we figure out the structure of the grid, we just need to recursively fill in this grid by grabbing the mid position for each recursive call. This is again due to the nature of how binary trees are structured: each node is the root of a subtree and each node will split into two nodes except for the last level.

        def printTree(self, root):
    
            def max_depth(root): # method for getting max depth
                if not root: return 0
                return max(max_depth(root.left), max_depth(root.right)) + 1
            
            def fill_grid(root, grid, lv, i, j): # recursive method for filling predetermined grid
                if root:
                    m = i + (j-i) // 2 # mid point
                    grid[lv][m] = str(root.val); lv += 1 # lv ++
                    fill_grid(root.left, grid, lv, i, m-1) # left child
                    fill_grid(root.right, grid, lv, m+1, j) # right child
                                    
            d = max_depth(root)
            width = (1 << d) - 1 # width of printed result
            grid = [['' for _ in range(width)] for _ in range(d)]
            fill_grid(root, grid, 0, 0, width-1)
            return grid
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.