Path Sum III

1. Problem Description

Given a binary tree, each node stores an integer value.

Find the total number of paths whose sum equals the given value.

A path does not need to start at the root or end at a leaf, but it must go downward (from parent to child only).

The binary tree contains at most 1000 nodes, and node values are integers in the range [-1000000,1000000].

2. Approach

1. Approach 1
   • Recursion
   • Count paths that include root and paths that do not include root

3. Implementation

3.1. Recursion

func pathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}

	return pathSumDFS(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

func pathSumDFS(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	count := 0
	if root.Val == sum {
		count += 1
	}
	count += pathSumDFS(root.Left, sum-root.Val)
	count += pathSumDFS(root.Right, sum-root.Val)
	return count
}

4. References

• 437. Path Sum III - LeetCode