437. Path Sum III #

Problem #

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• 109 <= Node.val <= 109
• 1000 <= targetSum <= 1000

Summary #

Given a binary tree, each node stores an integer value. Find the total number of paths whose path sum equals the given value. The path does not need to start from the root node, nor does it need to end at a leaf node, but the path direction must be downward (only from parent nodes to child nodes). The binary tree has no more than 1000 nodes, and the node values are integers in the range [-1000000,1000000].

Solution Ideas #

• This problem is an enhanced version of Problem 112 Path Sum and Problem 113 Path Sum II. This problem requires finding the sum of any path equal to sum; the starting point does not have to be the root node and can start from any node.
• Note that negative numbers may appear in this problem. A node sum equal to sum is not necessarily the final situation; there may be positive and negative nodes below that add up to exactly 0, which is also a valid case. Be sure to traverse to the end.
• Whether a node is the starting point for sum has 3 cases. In the first case, the path includes this root node. If it includes this node, then search in its left and right subtrees for cases where the sum is sum-root.Val. In the second case, the path does not include this root node, so you need to separately search in its left and right subtrees for nodes whose sum is sum.

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// Solution 1: DFS with caching
func pathSum(root *TreeNode, targetSum int) int {
	prefixSum := make(map[int]int)
	prefixSum[0] = 1
	return dfs(root, prefixSum, 0, targetSum)
}

func dfs(root *TreeNode, prefixSum map[int]int, cur, sum int) int {
	if root == nil {
		return 0
	}
	cur += root.Val
	cnt := 0
	if v, ok := prefixSum[cur-sum]; ok {
		cnt = v
	}
	prefixSum[cur]++
	cnt += dfs(root.Left, prefixSum, cur, sum)
	cnt += dfs(root.Right, prefixSum, cur, sum)
	prefixSum[cur]--
	return cnt
}

// Solution 2
func pathSumIII(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	res := findPath437(root, sum)
	res += pathSumIII(root.Left, sum)
	res += pathSumIII(root.Right, sum)
	return res
}

// Find paths that include the root node and whose sum is sum
func findPath437(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	res := 0
	if root.Val == sum {
		res++
	}
	res += findPath437(root.Left, sum-root.Val)
	res += findPath437(root.Right, sum-root.Val)
	return res
}