113. Path Sum II

题目

给定一个二叉树根节点 root 和一个整数 targetSum，返回所有从根节点到叶子节点 的和与目标值相同的路径。每个路径代表的是节点中的值。

解析

采用中序遍历的方式，递归遍历到叶子节点时，判断路径和，如果等于目标值，则以数组的形式返回，在非叶子节点返回的时候，合并左右子树的返回结果作为返回值返回。
所以这个递归函数原型

• 参数 target int 目标值
• 参数 sum int 已遍历路径之和
• 参数 node 当前节点
• 返回值 paths [][]int 符合要求的节点路径
  f(target, sum, node) paths

伪代码

if node == nil
  return [][]int{}
if node.left == nil && node.right == nil && target == sum + node.val
  return [][]int{{node.val}}
rst1 = f(target, sum+node.val, node.left)
rst2 = f(target, sum+node.val, node.right)
for i,_  in rst1
  rst1[i] = append([]int{node.val}, rst1[i]...)
for i,_  in rst2
  rst2[i] = append([]int{node.val}, rst2[i]...)
rst1 = append(rst1, rst2...)
return rst1

代码

func pathSum(root *TreeNode, targetSum int) [][]int {
    return f(targetSum, 0, root)
}

func f(target int, sum int, node *TreeNode) [][]int {
    if node == nil {
        return [][]int{}
    }
    if node.Left == nil && node.Right == nil && target == sum + node.Val {
        return [][]int{{node.Val}}
    }
    
    rst1 := f(target, sum+node.Val, node.Left)
    rst2 := f(target, sum+node.Val, node.Right)
    
    for i, _ := range rst1 {
        rst1[i] = append([]int{node.Val}, rst1[i]...)
    }
    for i, _ := range rst2 {
        rst2[i] = append([]int{node.Val}, rst2[i]...)
    }
    rst1 = append(rst1, rst2...)
    return rst1
}