java - 查找在二叉树中加起来总和的路由数

Question

给定一棵二叉树，其中每个节点都包含一个整数值。

找出总和为给定值的路径数。

路径不需要在根或叶开始或结束，但它必须向下(仅从父节点行进到子节点)。

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

class Solution {
    int count = 0;
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return helper(root, sum) + helper(root.left, sum) + helper(root.right, sum);
    }
    public int helper(TreeNode root,int sum) {
        if(root == null) {
            return 0;
        } else {
            sum -= root.val;
            if(sum == 0) {
                return 1 + pathSum(root.left,sum) + pathSum(root.right,sum);
            } else {
                return pathSum(root.left,sum) + pathSum(root.right,sum);
            }
        }        
    }
}

答案应该是 3，但我的答案返回 4，我不知道为什么。

Answer 1

您想为您的算法定义两种情况。

• 情况 1:您正在搜索可能存在于当前节点下的路径。
• 情况 2:您正在搜索包含当前节点的路径。

您可以定义 pathSum() 遵循情况​​ 1，定义 helper() 遵循情况​​ 2。这样，您可以使用 pathSum() 遍历树，并在任何节点调用 helper() 以检查从该节点开始的有效路径。

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    return pathSum(root.left, sum) + pathSum(root.right, sum) //Case 1: check for sum below current node 

    + helper(root, sum); //Case 2: check for sum starting from current node
}
public int helper(TreeNode root, int sum) {
    if (root == null) return 0;
    sum -= root.val; 
    if (sum == 0) {
        return 1; //if sum equals 0, we have a complete path, no need to go further
    }

    //else we do not have a complete path, continue searching in left and right child nodes
    return helper(root.left, sum) + pathSum(root.right, sum);
}