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

Question

给出一个二叉树，其中每个节点都包含一个整数值。 查找总和给定值的路径数。 路径不需要在根或叶子处开始或结束，但它必须向下（仅从父节点行进到子节点）。

我写这件事：

编辑：固定算法中，但未能上一个测试用例。

/** 
* 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 + (-2) = 8，路径10 -> 5 -> 3 -> -2也将成为解决方案的一部分。

现在要修复：
您需要跟踪可以通过树中的特定路径找到的所有和。解决这个的办法是保持数的累积列表：

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; 
} 

该解决方案表示为节点的值的列表的路径，并认为在当前节点结束所有的子序列，其总和达到给定值。这样路径不会被覆盖两次。