剑指Offer 34. 二叉树中和为某一值的路径

xiaoXingcode-go / 2023-08-28 / 原文

题目链接： 剑指Offer 34. 二叉树中和为某一值的路径

题目描述：

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

解法思路：

本题比较简单，就是一个遍历、回溯，在遍历的过程中，将非叶子节点的值都加到路径中，直到叶子节点的时候，判断当前路径的和是否与target相等，

相等，就将当前路径加到结果集中；
不相等，就递归下一层；
最后恢复现场；

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res [][]int
var path []int
func pathSum(root *TreeNode, target int) [][]int {
    res =[][]int{}
    path = []int{}
    dfs(root,target,0)
    return res 
}
func dfs(root *TreeNode, t int,sum int){

    if root == nil {
        return
    }
    sum += root.Val
    path = append(path,root.Val)
    if root.Left == nil && root.Right == nil {
        if sum == t{
            tmp := make([]int,len(path))
            copy(tmp,path)
            res = append(res,tmp)
            
        }
        
    }
   
    dfs(root.Left,t,sum)
    dfs(root.Right,t,sum)
        path = path[:len(path)-1]
}