1

我正在尝试创建一个函数来测试是否有一条路径可以总结为我的价值sum1。我不确定为什么我的函数出错了，但我从输出中假设它运行了太多次。我的树似乎在递归运行的前几次正常工作，但随着它越来越深入递归，它似乎做的太多了

输入：

hasPathSum(r,20)

输出：

has Path sum?
12
7
5
False

我的功能：

def hasPathSum(root,sum1):
    # Given a tree and a sum, return true if there is a path from the root
    # down to a leaf, such that adding up all the values along the path
    # equals the given sum
    # Strategy: Subtract the node value from the sum when recurring down,
    # and check to see if the sum is 0 when you run out of tree
    if not root:   # negative values? make sum == 0?
        return False
    else:
        sum1 = sum1 - root.value
        if sum1 == 0:
            return True
        else:
            if root.left is not None:
                print sum1
                return hasPathSum(root.left, sum1)
            if root.right is not None:
                print sum1
                return hasPathSum(root.right, sum1)
        return False

我的树：

r = Node(8)

#left

a = Node(5)
b = Node(2)
c = Node(1)
d = Node(3)
e = Node(7)

#right


f = Node(14)
g = Node(11)
h = Node(10)
i = Node(15)
j = Node(19)
k = Node(20)
l = Node(21)

BST_Insert(r, a)
BST_Insert(r, b)
BST_Insert(r, c)
BST_Insert(r, d)
BST_Insert(r, e)
BST_Insert(r, f)
BST_Insert(r, g)
BST_Insert(r, h)
BST_Insert(r, i)
BST_Insert(r, j)
BST_Insert(r, k)
BST_Insert(r, l)
4

0 回答 0