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

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

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 29 จากรูท หากเราทำตามเส้นทาง 5-<9-<7-<8 มันจะเป็น 29 หลังจากบวกแล้ว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้-

• กำหนดฟังก์ชั่น walk() นี่จะใช้โหนด s

• หากโหนดเป็นโมฆะ

  • max_sum :=สูงสุดของ max_sum และ s

  • กลับ

• s :=s + ข้อมูลของโหนด

• เดิน (ซ้ายของโหนด s)

• เดิน(ขวาของโหนด s)

• จากวิธีหลักให้ทำดังนี้:

• max_sum :=0

• เดิน(รูท, 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