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

สมมติว่าเรามีต้นไม้ไบนารี (Binary Tree) เราต้องการหาเส้นทางที่ยาวที่สุดที่ประกอบด้วยค่าคู่ (Even values) ระหว่างโหนดใดๆ สองโหนดในต้นไม้

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

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

1. กำหนด ans = 0
2. สร้างฟังก์ชัน find(node):
   • หาก node เป็น null ให้คืนค่า (-1, -1)
   • leftCnt = max(find(node.left)) + 1
   • rightCnt = max(find(node.right)) + 1
   • หากค่าของ node เป็นเลขคู่:
     • ans = max(ans, leftCnt + rightCnt + 1)
     • คืนค่า (leftCnt, rightCnt)
   • มิฉะนั้น:
     • ans = max(ans, leftCnt, rightCnt)
     • คืนค่า (-1, -1)
3. จากเมธอดหลัก เรียก find(root)
4. คืนค่า ans

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

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))  # Output: 5

อินพุต

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