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

สมมติว่าเรามีต้นไม้ไบนารี (binary tree) เราต้องการหาความยาวของเส้นทางที่มีผลรวมเป็นเลขคู่ (even sum)

เช่น ถ้าข้อมูลนำเข้าตามรูปภาพ ผลลัพธ์จะเป็น 5 เนื่องจากเส้นทางคือ [5, 2, 4, 8, 5] ผลรวม = 24 (เลขคู่)

ขั้นตอนการแก้ปัญหา (DFS ส่งค่าคู่)

• ฟังก์ชัน dfs(node) คืนคู่ (even_len, odd_len) คือความยาวเส้นทางที่ลงมาจากโหนดนี้ที่มีผลรวมคู่/คี่
• ถ้า node is None คืน (0, -inf)
• เรียก dfs ซ้ายและขวา ได้ (left_0, left_1), (right_0, right_1)
• ถ้า node.val เป็นเลขคี่:
  • อัปเดตคำตอบ: max(left_1 + right_0 + 1, left_0 + right_1 + 1)
  • คืน (max(left_1+1, right_1+1, 0), max(left_0+1, right_0+1))
• มิฉะนั้น (เลขคู่):
  • อัปเดตคำตอบ: max(left_0 + right_0 + 1, left_1 + right_1 + 1)
  • คืน (max(left_0+1, right_0+1, 0), max(left_1+1, right_1+1))

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

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