java - 与树相关的递归

Question

这是找到等于特定总和的根到叶路径的代码:

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }  
    if (root.left==null && root.right==null) {
        return (sum == root.val);
    }   
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

即使一个递归调用返回 true(使用 return (sum==root.val))，我也不明白原始函数调用如何为真。

我的理解是，在堆栈中，那个特定的激活记录是真的，但是堆栈上的其他调用不会返回假；显然剩下的可能不是一条路，这不会使它全部变成错误的吗？它如何重视那个 if 语句？

Answer 1

这实际上并没有以最清晰的方式编码。

递归总是通过使用相同的过程(函数)解决同一问题的一个或多个较小版本，然后组合这些解决方案来解决问题。

在这种情况下，较小的问题是检查左右子树(如果存在)中所需总和的其余部分。

如果成功，我们可以在左边停止，跳过右边。以这种方式，找到树中具有所需总和的“最左边”路径。我们不需要找到任何其他人。

检查子树时，我们从所需的总和中减去当前节点的值。直觉上，这会使问题“变小”，如上所述。

我将添加说明逻辑的注释。

public boolean hasPathSum(TreeNode root, int sum) {
    // If we've reached a null child, the other child is non-null,  so we're
    // not at a leaf, so there no way this can be a leaf-to-path sum.
    // See below for why this is the case.
    if (root == null) {
        return false;
    }
    // If we're at a leaf (null children), then we've found the path
    // if and only if the node value exactly equals the sum we're looking for. 
    if (root.left == null && root.right == null) {
        return (sum == root.val);
    }
    // We're not at a leaf.  See if we can find the remaining part of the sum
    // by searching the children.  Null children are handled above.  If the
    // sum is found in the left subtree, the short-circuit evaluation of ||
    // will skip searching the right.
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

请注意，这可能没有意义

hasPathSum(null, 0)

在此代码中返回 false。我会这样做:

class TreeNode {
    // ... skipping other TreeNode fields.
    public boolean isLeaf() { return left == null && right == null; } 
    public boolean hasPathSum(int sum) {
        return isLeaf() ? sum == val : 
            (left != null && left.hasPathSum(sum - val)) ||
            (right != null && right.hasPathSum(sum - val);
    }
}