โปรแกรมหาผลรวมซับทรีที่พบบ่อยที่สุดในต้นไม้ทวิภาคใน Python

สมมติว่าเรามีต้นไม้ทวิภาค ต้องหาผลรวมซับทรี (subtree sum) ที่พบบ่อยที่สุด ผลรวมซับทรีของโหนดคือผลรวมค่าทั้งหมดใต้โหนดนั้นรวมตัวมันด้วย

ตัวอย่าง: จากภาพ ผลลัพธ์คือ 3 เพราะเกิดขึ้น 2 ครั้ง (โหนดใบซ้าย และผลรวม 3 - 6 + 6)

ขั้นตอนการแก้ปัญหา

1. count = defaultdict(int)
2. ฟังก์ชัน getSum(node):
   • ถ้า node เป็น None: คืนค่า 0
   • mySum = getSum(node.left) + getSum(node.right) + node.val
   • count[mySum] += 1
   • คืนค่า mySum
3. จากเมธอดหลัก เรียก getSum(root)
4. คืนค่า max(count, key=count.get)

ตัวอย่างโค้ด Python

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

อินพุต / เอาต์พุต

Input: ต้นไม้ตามโค้ดตัวอย่าง

Output: 3