โปรแกรมหาผลรวมตัวเลขจากเส้นทางรากถึงใบของต้นไม้แบบทวิภาคใน Python

ต้นไม้แบบทวิภาคแต่ละโหนดมีตัวเลข 0-9 เส้นทางจากรากถึงใบแทนตัวเลข หาผลรวมทุกเส้นทาง

เช่น ต้นไม้ราก 4 ซ้าย 6 ขวา 3 (ซ้าย 2 ขวา 5) ให้ 46+432+435=913

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

• ฟังก์ชัน solve(root, string) สร้างสตริงตัวเลขตามเส้นทาง
• ถ้าเป็นใบ คืนค่า int(string + str(root.val))
• รวมผลลัพธ์จากซ้ายและขวา

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

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, string=""):
        if root and not root.left and not root.right:
            return int(string + str(root.val))
        total = 0
        if root.left:
            total += int(self.solve(root.left, string + str(root.val)))
        if root.right:
            total += int(self.solve(root.right, string + str(root.val)))
        return total

ob = Solution()
root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)
print(ob.solve(root))

อินพุต

root = TreeNode(4) ...

เอาต์พุต

913