Chương trình tìm độ rộng tối đa của cây nhị phân trong Python

Cho cây nhị phân, tìm độ rộng tối đa của bất kỳ cấp độ nào. Độ rộng của một cấp là số nút có thể chứa giữa nút trái nhất và nút phải nhất.

Ví dụ (cây minh họa): Đầu ra 2.

Các bước giải quyết (DFS với vị trí):

• Tạo từ điển d lưu cặp (min, max) cho mỗi độ sâu, khởi tạo min = inf, max = 0.
• Định nghĩa dfs(node, pos=0, depth=0):
  • Nếu node là None, trả về.
  • Cập nhật d[depth][0] = min(d[depth][0], pos), d[depth][1] = max(d[depth][1], pos).
  • Gọi đệ quy cho con trái: dfs(node.left, 2*pos, depth+1).
  • Gọi đệ quy cho con phải: dfs(node.right, 2*pos+1, depth+1).
• Gọi dfs(root).
• mx := 0. Duyệt các cặp min-max trong d.values(): mx = max(mx, right - left + 1).
• Trả về mx.

Ví dụ minh họa

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 interval in d.values():
            l, r = interval
            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))

Đầu vào

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)

Đầu ra

2