Python, concise and easy understand BFS


  • 0
    C

    use bfs to search level by level. The width of a level is the last element index - the first element index. The index can be calculated by its parent nodes, that is if the parent node index is i, then in binary tree its left child 2i-1 and right child 2i

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def widthOfBinaryTree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            q = [(root, 1)]
            res = 1
            while q:
                nextlevel = []
                for node in q:
                    if node[0].left:
                        nextlevel.append((node[0].left, 2 * node[1] - 1))
                    if node[0].right:
                        nextlevel.append((node[0].right, 2 * node[1]))
                if len(nextlevel) >= 2:
                    res = max(res, nextlevel[-1][1] - nextlevel[0][1] + 1)
                q = nextlevel    
            return res

Log in to reply
 

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