34. 二叉树中和为某个值的路径

题目

输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

二叉树节点定义如下：

type TreeNode struct {
	val   int
	left  *TreeNode
	right *TreeNode
}

假设有如下二叉树：

        10 
    5        12
  4   7

目标和为22，则打印出两条路径：[10, 5, 7], [10, 12]

解题思路

先序遍历。遍历到某个节点时，把节点保存下来，并且累计求和。如果遇到叶子节点，而且和正好为目标值，则打印路径。否则，继续遍历非空左右子节点。

在返回父节点前，需要在路径上删除当前节点。

实现代码

func FindPath(root *TreeNode, targetSum int) [][]int {
	if root == nil {
		return nil
	}

	var path []int
	var paths [][]int
	curSum := 0
	doFindPaths(root, targetSum, curSum, path, &paths)
	return paths
}

func doFindPaths(root *TreeNode, targetSum int, curSum int, path []int, paths *[][]int) {
	path = append(path, root.val)
	curSum += root.val
	if isLeaf(root) && curSum == targetSum {
		*paths = append(*paths, path)
		fmt.Printf("find path:%v", path)
	}

	if root.left != nil {
		doFindPaths(root.left, targetSum, curSum, path, paths)
	}

	if root.right != nil {
		doFindPaths(root.right, targetSum, curSum, path, paths)
	}
	//返回父节点前，在路径上删除当前节点
	path = path[:len(path)-1]
}

func isLeaf(node *TreeNode) bool {
	return node.left == nil && node.right == nil
}