Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- class TreeNode:
- def __init__(self, val=0, left=None, right=None):
- self.val = val
- self.left = left
- self.right = right
- def constructTree(nodes):
- if not nodes:
- return None
- root = TreeNode(nodes[0])
- q = deque()
- q.append(root)
- i = 1
- while q and i < len(nodes):
- parent = q.popleft()
- leftVal = nodes[i]
- rightVal = nodes[i+1] if i+1 < len(nodes) else None
- i += 2
- if leftVal is not None:
- parent.left = TreeNode(leftVal)
- q.append(parent.left)
- if rightVal is not None:
- parent.right = TreeNode(rightVal)
- q.append(parent.right)
- return root
- def maxwidth(root):
- if not root:
- return 0
- maxWidth = float('-inf')
- q = deque()
- q.append((root, 0))
- while q:
- size = len(q)
- left, right = float('inf'), float('-inf')
- for _ in range(size):
- node, pos = q.popleft()
- left = min(left, pos)
- right = max(right, pos)
- if node.left:
- q.append((node.left, 2 * pos))
- if node.right:
- q.append((node.right, 2 * pos + 1))
- maxWidth = max(maxWidth, right - left + 1)
- return maxWidth
- # Example usage:
- n = int(input())
- nodes = list(map(int, input().split()))
- root = constructTree(nodes)
- maxWidth = maxwidth(root)
- print(maxWidth)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement