# Max Width of Binary Tree

O(n)遍历是可以做的，我Google面试时也只想到这个。DFS可以变成O(log(n)) 需要意识到

（1）一点如果parent是i, left child 的index就是2\*i，right是2\*i+1

（2）我们一个dictionary来记录每一个level最左边的点，也就是depth第一次更新时的pos，然后通过left和后面的同level的pos 的差来求出最大possible 的width

代码

```python
class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        self.left = dict()
        self.res = 0
        def dfs(node,depth,pos):
            if node == None:
                return
            if depth not in self.left:
                self.left[depth] = pos
            self.res = max(self.res,pos-self.left[depth]+1)
            dfs(node.left,depth+1,pos*2)
            dfs(node.right,depth+1,pos*2+1)
        dfs(root,0,0)
        return self.res
```