使用Python的一种神奇的BFS写法

Leetcode 662

class Solution:
    def widthOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        q = [(root, 0, 0)] # (node, depth, position)
        cur_depth, left, ans = 0, 0, 0
        for (node, depth, pos) in q:
            if node:
                q.append((node.left, depth+1, 2*pos))
                q.append((node.right, depth+1, 2*pos+1))
                if depth != cur_depth:
                    cur_depth = depth
                    left = pos
                ans = max(pos-left+1, ans)
        return ans