breadth first, only need start and end. find the first not none from left and from right

because None in the middle has no parents, we cannot use array. next breadth are based on previous. If prv has breadth of 3, then there will be 6 at most in the next. remove only None in the head and tail.

"""

class Solution(object):

def widthOfBinaryTree(self, root):

"""

:type root: TreeNode

:rtype: int

"""

if not root:

return 0

brd = 2

mxbrd = 1

curr = [root.left, root.right]

while any(curr):

l, r = 0, 0

for i in curr:

if not i:

l += 1

else:

break

for i in curr[::-1]:

if not i:

r += 1

else:

break

brd = brd - l - r

mxbrd = max(brd, mxbrd)

curr = [k for p in curr if p for k in (p.left, p.right)]

brd *= 2

return mxbrd

"""