爲什麼這個算法不適用於樹中的路徑和？

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

該解決方案表示爲節點的值的列表的路徑，並認爲在當前節點結束所有的子序列，其總和達到給定值。這樣路徑不會被覆蓋兩次。