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

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

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

แล้วผลลัพธ์จะเป็น 20

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

• กำหนดฟังก์ชัน rec() การดำเนินการนี้จะใช้เวลาสักครู่

• ถ้าค่าเงินเป็นโมฆะ

  • ผลตอบแทน(0, 0)

• ใหญ่กว่า :=สูงสุดของ rec(ซ้ายของสกุลเงิน), rec(ขวาของสกุลเงิน)

• ส่งคืนค่าคู่ (ใหญ่กว่า[0] + 1 ใหญ่กว่า[1] + มูลค่าของสกุลเงิน)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ret :=rec(root)

• คืนค่าดัชนีที่ 1 ของ ret

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

class Solution:
   def solve(self, root):
      def rec(curr):
         if not curr:
            return (0, 0)
         bigger = max(rec(curr.left), rec(curr.right))
         return (bigger[0] + 1, bigger[1] + curr.val)
      return rec(root)[1]
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

อินพุต

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

ผลลัพธ์

20