Tổng đường đi trong Python

Cho cây nhị phân và tổng sum. Tìm đường đi từ gốc đến lá có tổng bằng sum. Ví dụ: cây [0,-3,9,-10,null,5], sum=14 → đường 0→9→5.

Giải pháp

Đệ quy:

• Nếu gốc rỗng → False.
• Nếu nút lá: trả về sum - root.val == 0.
• Trả về solve(left, sum-root.val) OR solve(right, sum-root.val).

Ví dụ

Triển khai Python:

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): 
        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))

Đầu vào

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

Đầu ra

True