Chương trình tìm tổng cây con xuất hiện nhiều nhất trong cây nhị phân bằng Python

Cho cây nhị phân, tìm tổng cây con (subtree sum) xuất hiện nhiều nhất. Tổng cây con của nút là tổng giá trị tất cả nút trong cây con gốc tại nút đó (kể cả chính nút đó).

Ví dụ: cây có nút gốc -6, con trái 3, con phải 6 → tổng 3 xuất hiện 2 lần (lá 3 và cây con -6+3+6=3) → kết quả 3.

Quy trình giải quyết

1. Dùng defaultdict(int) đếm tần suất tổng.
2. Đệ quy getSum(node): trả về 0 nếu null, ngược lại tính tổng = getSum(left) + getSum(right) + node.val, tăng đếm, trả về tổng.
3. Gọi getSum(root).
4. Trả về khóa có giá trị lớn nhất trong từ điển đếm.

Ví dụ mã nguồn

from collections import defaultdict

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.val = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        count = defaultdict(int)
        def getSum(node):
            if not node:
                return 0
            mySum = getSum(node.left) + getSum(node.right) + node.val
            count[mySum] += 1
            return mySum
        getSum(root)
        return max(count, key=count.get)

ob = Solution()
root = TreeNode(-6)
root.left = TreeNode(3)
root.right = TreeNode(6)
print(ob.solve(root))  # Output: 3

Đầu vào

root = TreeNode(-6) root.left = TreeNode(3) root.right = TreeNode(6)

Đầu ra

3