โปรแกรมค้นหาเส้นทางค่าคู่ที่ยาวที่สุดของไบนารีทรีใน Python

สมมติว่าเรามีไบนารีทรี เราต้องหาเส้นทางที่ยาวที่สุดซึ่งประกอบด้วยค่าคู่ระหว่างสองโหนดในทรี

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

จากนั้นผลลัพธ์จะเป็น 5 เนื่องจากเส้นทางที่ยาวที่สุดคือ [10, 2, 4, 8, 6]

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

• ตอบ :=0

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

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

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

• leftCnt :=ค่าสูงสุดที่ส่งคืนของ find (ซ้ายของโหนด) + 1

• rightCnt :=ค่าสูงสุดที่ส่งคืนของ find(right of node) + 1

• ถ้าค่าของโหนดเป็นคู่ ดังนั้น

  • ans :=สูงสุดของ ans และ (leftCnt + rightCnt + 1)

  • กลับ (leftCnt, rightCnt)

• มิฉะนั้น

  • ans :=สูงสุดของ ans, leftCnt และ rightCnt

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

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

• ค้นหา (ราก)

• กลับมาอีกครั้ง

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

ตัวอย่าง

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):
      ans = 0
      def find(node):
         nonlocal ans
         if not node:
            return -1, -1
         leftCnt = max(find(node.left)) + 1
         rightCnt = max(find(node.right)) + 1
         if node.val % 2 == 0:
            ans = max(ans, leftCnt + rightCnt + 1)
            return leftCnt, rightCnt
         else:
            ans = max(ans, max(leftCnt, rightCnt))
            return -1, -1
      find(root)
      return ans
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)

ผลลัพธ์

5