递归方法解leetcode之113-路径总和II

题目描述:

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的节点

解题思路:

能想到的只有递归，用递归解起来感觉还是比较简单，但还有细节需要注意

1. 要遍历整个树，不能像之前的找到true就可以返回
2. 因为要修改切片的值，所以这里要传入切片的地址，在追加的时候，又要解引用
3. re不能传入引用，在最终追加进res之前，需要复制一个切片出来，不然会因为栈调用覆盖掉原来的值。这在里填坑填了好久。明明进res的是正确的值，结果仍被覆盖...

golang示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
    results := [][]int{}
    re := []int{}
    getNode(root, targetSum, re, &results)
    return results
}


func getNode(root *TreeNode, targetSum int, re []int, res *[][]int) {
    if root == nil {
        return
    }
    lst := make([]int, len(re))
    // 这里是重点，有时会覆盖掉了原来的,所以复制一份出来
    re = append(re, root.Val)
    copy(lst, re)
    if root.Left == nil && root.Right == nil && root.Val == targetSum {
        // 最后追加的时候，用复制出来的切片,如果修改追加为re，再res追加re。打印的也是正确的值，但最终结果却是错的
        lst = append(lst, root.Val)
        // 解引用
        *res = append(*res, lst)
    }
    getNode(root.Left, targetSum - root.Val, re, res)
    getNode(root.Right, targetSum - root.Val, re, res)
}

文章目录