Python BFS solution using queue, no recursion.


  • 0
    Y

    The idea is straightforward,

    1. calculate the height, so the column n will be pow(2, h)-1
    2. for each row, it will have count=pow(2, i) numbers so each number will take n / count space, because we need to put them in the middle of their space so the first of each row postion is n / count / 2, the next one will be n / count / 2 + n / count + 1 on the right side, then next next is n / count / 2 + n / count + 1 + n / count + 1 .... so we can conclude the position of number j in each row is: n / count / 2 + j * (n / count + 1) here each time add 1 because their direct parent will take up one space (see problem example 1, 2nd row is '2', '', '', the middle '' is taken by previous '1'
    3. just put the number in their position and append each row to the final result
    class Solution(object):
        def getHeight(self, root):
            if root is None:
                return 0
            return 1 + max(self.getHeight(root.left), self.getHeight(root.right))
        
        def printTree(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[str]]
            """
            res = []
            h = self.getHeight(root)
            n = pow(2, h) - 1
            q = [root]
            for i in range(0, h):
                lvl = [''] * n
                count = pow(2, i)
                for j in range(0, count):
                    top = q.pop(0)
                    pos = j * (n / count + 1) + n / count / 2
                    val = ''
                    left = None
                    right = None
                    if top is not None:
                        val = str(top.val)
                        left = top.left
                        right = top.right
                    lvl[pos] = val
                    q.append(left)
                    q.append(right)
                res.append(lvl)
            return res
    

Log in to reply
 

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