โปรแกรมหาผลรวมสูงสุดของเส้นทางใดๆ ในต้นไม้ไบนารีใน Python

สมมติว่ามีต้นไม้ไบนารี เราต้องหาผลรวมสูงสุดของเส้นทางใดๆ ที่ไปจากรากถึงใบ

เช่น ถ้าอินพุตเป็นต้นไม้ดังภาพ ผลลัพธ์จะเป็น 29 เส้นทาง 5-9-7-8

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

• กำหนดฟังก์ชัน walk() รับ node, s
  • ถ้า node เป็น null max_sum := max(max_sum, s) คืนค่า
  • s := s + node.data
  • walk(left of node, s), walk(right of node, s)
• จากเมธอดหลัก max_sum := 0 walk(root, 0) คืนค่า max_sum

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

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 walk(self, node, s):
        if not node:
            self.max_sum = max(self.max_sum, s)
            return
        s += node.data
        self.walk(node.left, s)
        self.walk(node.right, s)
    def solve(self, root):
        self.max_sum = 0
        self.walk(root, 0)
        return self.max_sum

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))

อินพุต

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)

เอาต์พุต

29