662. Maximum Width of Binary Tree

Loading...LeetCode

二叉树层序遍历有关的问题 => BFS

需要求当前层的width，空node还要占位，只好传递更新一下在当前层的位置。

class Solution:
    def __init__(self):
        self.maxWidth = 0
        
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        q = collections.deque([(root, 0)])
        while q:
            n = len(q)
            level = []
            for _ in range(n):
                cur, p = q.popleft()
                level.append(p)
                if cur.left: q.append((cur.left, p*2))
                if cur.right: q.append((cur.right, p*2+1))
            self.maxWidth = max(self.maxWidth, level[-1]-level[0]+1)
        return self.maxWidth if root else root

时间复杂度卡得好严格，写了个理论上worst case O(n+n**log(n))的方法都过不了...