โปรแกรมหาความยาวของพาธที่ยาวที่สุดด้วยผลรวมคู่ใน Python

สมมติว่าเรามีต้นไม้ไบนารี เราต้องหาความยาวของเส้นทางที่ยาวที่สุดซึ่งผลรวมเป็นเลขคู่

ดังนั้น หากอินพุตเป็นเหมือนรูปภาพ ผลลัพธ์จะเป็น 5 เนื่องจากพาธเป็นเหมือน [5, 2, 4, 8, 5], sum =24(คู่)

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

• กำหนดฟังก์ชัน dfs() นี่จะใช้โหนด
• ถ้าโหนดเป็น null แล้ว
  • คืนคู่ (0, -inf)
• (left_0, left_1) :=dfs(ซ้ายของโหนด)
• (right_0, right_1) :=dfs(ทางขวาของโหนด)
• ถ้าค่าของโหนดเป็นเลขคี่
  • ans :=สูงสุดของ ans, (left_1 + right_0 + 1) และ (left_0 + right_1 + 1)
  • ส่งคืนคู่ (สูงสุด (left_1 + 1), (right_1 + 1) และ 0) , สูงสุด (left_0 + 1) และ (right_0 + 1))
• มิฉะนั้น
  • ans :=สูงสุดของ ans, (left_0 + right_0 + 1) และ (left_1 + right_1 + 1)
  • ส่งคืนคู่ (สูงสุด (left_0 + 1), (right_0 + 1), 0) , สูงสุดของ (left_1 + 1), (right_1 + 1))
• จากวิธีหลัก ให้ทำดังนี้ -
• ตอบ :=0
• dfs(root)
• คืนสินค้า

ตัวอย่าง (Python)

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

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):
      def dfs(node):
         if not node:
            return 0, float("-inf")
         left_0, left_1 = dfs(node.left)
         right_0, right_1 = dfs(node.right)
         if node.val & 1:
            self.ans = max(self.ans, left_1 + right_0 + 1, left_0 + right_1 + 1)
            return max(left_1 + 1, right_1 + 1, 0), max(left_0 + 1, right_0 + 1)
         else:
            self.ans = max(self.ans, left_0 + right_0 + 1, left_1 + right_1 + 1)
            return max(left_0 + 1, right_0 + 1, 0), max(left_1 + 1, right_1 + 1)
   self.ans = 0
   dfs(root)
   return self.ans
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)
print(ob.solve(root))

อินพุต

root = TreeNode(2)
root.left = TreeNode(5)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(5)

ผลลัพธ์

5