LeetCode讲解篇之113. 路径总和 II

题目描述

题解思路

深度优先遍历二叉树，遍历的同时记录路径，直到遍历到叶节点，若路径和为targetSum则添加到结果集中

题解代码

func pathSum(root *TreeNode, targetSum int) [][]int {
    var res = make([][]int, 0)
    path := make([]int, 0, 1)
    var sum func(root *TreeNode, targetSum int)
    sum = func (root *TreeNode, targetSum int) {
        if root == nil {
            return
        }
        targetSum -= root.Val
        path = append(path, root.Val)
        defer func() { path = path[:len(path)-1] }()
        if root.Left == nil && root.Right == nil && targetSum == 0 {
            res = append(res, append([]int{}, path...))
            return
        }
        sum(root.Left, targetSum)
        sum(root.Right, targetSum)
    }
    sum(root, targetSum)
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21