Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Definition for a binary tree node.
- # class TreeNode:
- # def __init__(self, val=0, left=None, right=None):
- # self.val = val
- # self.left = left
- # self.right = right
- class Solution:
- def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
- left_shift = [0]
- max_right = defaultdict(lambda: -float('inf'))
- def dfs(node: Optional[TreeNode], pos: int = 0, level: int = 0):
- if node is None:
- return
- if level != 0:
- if len(left_shift) == level:
- left_shift.append(pos)
- pos -= left_shift[level]
- max_right[level] = max(max_right[level], pos)
- dfs(node.left, pos * 2, level + 1)
- dfs(node.right, pos * 2 + 1, level + 1)
- dfs(root)
- return max(max_right.values()) + 1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement