java - 在二叉树中查找总和的路由数量

给出了一个二叉树，其中每个节点都包含一个整数值。
找到与给定值相加的路径数。
路径不需要从根或叶开始或结束，但必须向下（仅从父节点到子节点）。

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，我不知道为什么。

最佳答案

要为算法定义两个案例。
案例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);
}

关于java - 在二叉树中查找总和的路由数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57941697/