ความกว้างของระดับ: จำนวนตำแหน่งที่สามารถมีโหนดได้ระหว่างโหนดซ้ายสุดและขวาสุด (รวมช่องว่าง)
ใช้การจัดตำแหน่งแบบ heap: ราก=0, ลูกซ้าย=2*pos, ลูกขวา=2*pos+1 หาความกว้าง = max_pos - min_pos + 1 ทุกระดับ
อัลกอริธึม DFS
- DFS บันทึก min/max position ของแต่ละ depth
- คำนวณความกว้างแต่ละระดับ หาค่าสูงสุด
การนำไปใช้
from collections import defaultdict
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
d = defaultdict(lambda: [1e9, 0])
def dfs(node, pos=0, depth=0):
if not node:
return
d[depth][0] = min(d[depth][0], pos)
d[depth][1] = max(d[depth][1], pos)
dfs(node.left, 2*pos, depth+1)
dfs(node.right, 2*pos+1, depth+1)
dfs(root)
mx = 0
for l, r in d.values():
mx = max(mx, r - l + 1)
return mx
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root)) # 2
