113. Path Sum II

2022-06-14  本文已影响0人  sarto

题目

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

解析

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

伪代码

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
}
上一篇 下一篇

猜你喜欢

热点阅读