We could DFS or BFS to traverse the tree and mark the position for each node. For each node, its left node is the same position at itself and its right node is in its position plus 1.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def widthOfBinaryTree(self, root: TreeNode) -> int:
left_most = []
right_most = []
self._dfs(root, 0, 0, left_most, right_most)
return max([j - i + 1 for i, j in zip(left_most, right_most)])
def _dfs(self, node, depth, shift, left_most, right_most):
if node is None:
return
if depth >= len(left_most):
left_most.append(shift)
right_most.append(shift)
else:
right_most[depth] = shift
self._dfs(node.left, depth + 1, shift * 2, left_most, right_most)
self._dfs(node.right, depth + 1, shift * 2 + 1, left_most, right_most)