java - 为什么这个算法不适用于树中的路径和？

Question

You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

我写了这个:

编辑:修复了算法，但在测试用例上失败。

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    public int helper(TreeNode node, int sum){
        if(node == null) return 0;
        if(node.val == sum) return 1;
        return helper(node.left, sum - node.val) + helper(node.right, sum - node.val);
    }

}

Answer 1

在返回语句中包含这两个递归调用:

pathSum(root.right, sum) + pathSum(root.left, sum)

完成:

return pathSum(root.left, sum - root.val) + pathSum(root.right, sum - root.val) + pathSum(root.right, sum) + pathSum(root.left, sum);

这基本上意味着您允许遍历跳过路径中间的节点。例如。路径 10 -> 5 -> 3 -> -2 也将是解决方案的一部分，因为 10 + (-2) = 8。

现在修复:
您需要跟踪在树的特定路径上可以找到的所有总和。解决这个问题的一种方法是保留一个累积的数字列表:

public int pathSum(TreeNode n, Stack<Integer> acc, int sum){
    if(n == null){
        return 0;
    }

    int count = 0;
    int totalToNode = acc.peek() + n.val;

    //increment count, if the nodes value matches (path of length 1)
    if(n.val == sum)
        count++;

    //increment count, if the path from root to n sums up to the given value
    if(totalToNode == num)
        count++;

    //find all paths that end in n and sum up to the searched sum
    for(int s : acc)
        if(totalToNode - s == sum)
            count++;

    acc.push(totalToNode);

    //number of matching paths for left and right subtree
    count += pathSum(n.left, acc, sum);
    count += pathSum(n.right, acc, sum);

    acc.pop();

    return count;
}

该解决方案将路径表示为节点值列表，并查找以当前节点结束且总和为给定值的所有子序列。这样路径就不会被覆盖两次。