调试我的二叉树搜索求和算法

Question

问题很简单，我们已经检查是否存在根到叶的路径，其总和等于S(sum given to find)。

任务：完成函数 hasPathSum()，它将根节点和目标总和 S 作为输入参数，如果路径存在，则 returns 为真，否则为 returns 假。

根据我的调试，我的代码是正确的，但在少数测试用例中出现错误。我的代码如下

class Node:
    def __init__(self,val):
        self.data = val
        self.left = None
        self.right = None
def hasPathSum(root, S):
    '''
    :param root: root of given tree.
    :param sm: root to leaf sum
    :return: true or false
    '''
    if root==None:
        return 0
    if S==0:
        return 1
    if S==root.data:
        return 1
    if S>root.data:
        b=S-root.data
    else:
        return 0
    return hasPathSum(root.left,b) or hasPathSum(root.right,b)

Answer 1

我认为你应该在return为真

之前检查当前节点是否为叶节点

考虑一棵简单的树：

   2
 /  \
1    3

调用 hasPathSum(root, 2) 会 return 1 因为 S==root.data 为真，尽管它不是叶节点的路径。

您可以像这样修复它：

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

def hasPathSum(root, S):
    '''
    :param root: root of given tree.
    :param sm: root to leaf sum
    :return: true or false
    '''
    if root==None:
        return 0
    # we dont need the S == 0 condition 
    # since the sum can reach 0 before reaching the leaf node
    # check if root is leaf
    if S==root.data and root.left == None and root.right == None: 
        return 1
    if S>root.data:
        b=S-root.data
    else:
        return 0
    return hasPathSum(root.left,b) or hasPathSum(root.right,b)

调试我的二叉树搜索求和算法

debugging my binary tree searching sum algo

python

binary-tree