Binary Tree Maximum Path Sum ใน Python

กำหนด binary tree ไม่ว่าง ต้องหา maximum path sum โดย path คือลำดับโหนดที่เชื่อมต่อกัน parent-child มีอย่างน้อย 1 โหนด ไม่จำเป็นต้องผ่าน root

ตัวอย่าง tree: root=-10, left=9, right=10, right.left=15, right.right=7 → output 32 (path 15→10→7)

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

• ฟังก์ชัน solve(node) คืนค่า max path sum จาก node ลงไป (รวม node เอง)
• ถ้า node เป็น None หรือค่า 0 คืน 0
• left = max(0, solve(node.left)), right = max(0, solve(node.right))
• อัปเดต global ans = max(ans, left + right + node.data)
• คืนค่า node.data + max(left, right)

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

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

def insert(temp, data):
    que = [temp]
    while que:
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def maxPathSum(self, root):
        self.ans = -float('inf')
        self.solve(root)
        return self.ans
    def solve(self, node):
        if not node or node.data == 0:
            return 0
        left = max(0, self.solve(node.left))
        right = max(0, self.solve(node.right))
        self.ans = max(self.ans, left + right + node.data)
        return node.data + max(left, right)

ob = Solution()
root = make_tree([-10, 9, 10, None, None, 15, 7])
print(ob.maxPathSum(root))

อินพุต

[-10, 9, 10, None, None, 15, 7]

เอาต์พุต

32