题解 | #二叉树中和为某一值的路径(三)#

package main

// import "fmt"
import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @param sum int整型
 * @return int整型
 */
var res int

func FindPath(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	var dfs func(*TreeNode, int)
	dfs = func(root *TreeNode, target int) {
		if target == 0 {
			res++
		}
		if root == nil {
			return
		}
		if root.Left != nil {
			dfs(root.Left, target-root.Left.Val)
		}
		if root.Right != nil {
			dfs(root.Right, target-root.Right.Val)
		}
	}
	dfs(root, sum-root.Val)

	FindPath(root.Left, sum)
	FindPath(root.Right, sum)
	return res
}