013.路径总和III

• 437.路径总和 III
  • 回溯
  • 深度优先遍历
  • 前缀和

路径总和 III - 回溯

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
var (
	ans int
	theTarget int
	sums []int
)
 
func pathSum(root *TreeNode, targetSum int) int {
	ans = 0
	theTarget = targetSum
	sums = []int{}
	process(root)
 
	return ans >> 1
}
 
func process(root *TreeNode) {
	for _, sum := range sums {
		if sum == theTarget {
			ans++
		}
	}
	if root == nil {
		return
	}
	for i := range sums {
		sums[i] += root.Val
	}
	sums = append(sums, root.Val)
	process(root.Left)
	process(root.Right)
	sums = sums[:len(sums) - 1]
	for i := range sums {
		sums[i] -= root.Val
	}
}

路径总和 III - 深度优先遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}
 
	ans := rootSum(root, targetSum)
	ans += pathSum(root.Left, targetSum)
	ans += pathSum(root.Right, targetSum)
 
	return ans
}
 
// 以节点 root 为起点向下且满足路径总和为 targetSum 的路径数目
func rootSum(root *TreeNode, targetSum int) (ans int) {
	if root == nil {
		return
	}
 
	sub := targetSum - root.Val
	if sub == 0 {
		ans++
	}
	ans += rootSum(root.Left, sub)
	ans += rootSum(root.Right, sub)
	return
}

路径总和 III - 前缀和

先序遍历、前缀和 + map 记录

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) int {
	// key: sum
	// val: 次数
	preSum := map[int]int{ 0: 1 }
	ans := 0
	var dfs func(node *TreeNode, curSum int)
	dfs = func(node *TreeNode, curSum int) {
		if node == nil {
			return
		}
		curSum += node.Val
		ans += preSum[curSum - targetSum]
		preSum[curSum]++
		dfs(node.Left, curSum)
		dfs(node.Right, curSum)
		preSum[curSum]--
	}
	dfs(root, 0)
 
	return ans
}