BFS using python


  • 0
    S
    class Solution(object):
        def widthOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            width = 0
            if root:
                pos = 1
                cur = [ (root,pos) ]  # current level
                nxt = []   # next level
                while cur or nxt:
                    left  = float('inf')
                    right = -float('inf')
                    for node,pos in cur:
                        left  = min(left,pos)  # find left most index
                        right = max(right,pos) # find right most index
                        if node.left:
                            nxt += (node.left,2*pos),
                        if node.right:
                            nxt += (node.right,2*pos+1),
                    cur = nxt
                    nxt = []
                    width = max(width, right-left+1) # calculate width of previous level
            return width
    

Log in to reply
 

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