Path Sum ใน Python

สมมติว่าเรามีต้นไม้หนึ่งต้นและผลรวมหนึ่งค่า เราต้องหาเส้นทางหนึ่งเส้นทางที่ถ้าเราตามเส้นทางนั้น เราจะได้ผลรวมที่ตรงกับผลรวมที่กำหนด สมมติต้นไม้เป็น [0,-3,9,-10, null,5] และผลรวมคือ 14 แล้วมีเส้นทาง 0 → 9 → 5

วิธีการแก้ปัญหา

• ถ้ารากเป็น null ให้คืนค่า False
• ถ้าต้นไม้ย่อยซ้ายและขวาว่าง ให้คืนค่า true เมื่อ sum - root.val = 0 มิฉะนั้น false
• คืนค่า solve(root.left, sum - root.val) หรือ solve(root.right, sum - root.val)

ตัวอย่าง

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None

def insert(temp, data):
    que = []
    que.append(temp)
    while len(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 hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        if not root.left and not root.right and root.data is not None:
            return sum - root.data == 0
        if root.data is not None:
            return self.hasPathSum(root.left, sum - root.data) or self.hasPathSum(root.right, sum - root.data)

tree1 = make_tree([0,-3,9,-10,None,5])
ob1 = Solution()
print(ob1.hasPathSum(tree1, 14))

อินพุต

tree1 = make_tree([0,-3,9,-10,None,5])

เอาต์พุต

True