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
网友评论