class Solution:
def widthOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = 1
self.dfs(root, 1, 1, [])
return self.res
def dfs(self, root, level, index, start):
if not root: return
"""
start = [] [1] [1,2] [1,2,4]
level = 0 1 2 3
"""
if len(start) < level:
start.append(index)
else:
self.res = max(self.res, index - start[level-1] + 1)
self.dfs(root.left, level + 1, index * 2, start)
self.dfs(root.right, level + 1, index * 2 + 1, start)
