Paths with Sum II

Paths with Sum II

You are given a binary tree in which each node contains an integer value (which might be positive or negative). Design an algorithm to count 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)

Solution

暂时只想到暴力法

Code

// Brute Force
int countPath(TreeNode root, int sum){
    if (root == null)
        return 0;

    int pathsRoot = countPathFromNode(root, sum, 0);

    int pathsLeft = countPath(root.left, sum);
    int pathsRight = countPath(root.right, sum);

    return pathsRoot + pathsLeft + pathsRight;
}

int countPathFromNode(TreeNode node, int sum, int curSum){
    if (node == null){
        return 0;
    }

    curSum += node.data;

    int totalPath = 0;
    if (curSum == sum){
        totalPath++;
    }

    totalPath += countPathFromNode(node.left, sum, curSum);
    totalPath += countPathFromNode(node.right, sum, curSum);

    return totalPath;
}