题目

leetcode:112

代码与解析

路径总和，可以用递归加回溯

1.递归

递归三部曲

• 确定参数及返回值
  参数要传入当前节点， 然后还要传入总和，返回布尔类型，

• 确定终止条件
  当前节点是叶子结点 并且 和等于target， 那么返回true
  如果当前节点是叶子结点还不等于target返回false

• 单层递归逻辑
  因为终止条件是判断叶子节点，所以就不要让空节点进入了，
  递归是有返回值的，如果为true，那么就直接返回true.

关于 二叉树所有路径哪道题是一进递归就先添加path路径。而这里没有一开始就sum+=root.Val,原因一：那道题是前序遍历，而且要遍历整棵树，每个路径都需要，就和递归遍历二叉树返回数组差不多，这道题只需要判断sum是否等于target,回溯可以藏在函数调用里，调用完一切恢复原样。就相当于一个人拿着小棍探测。行的话我就这样走，路径记下来，不行的话我换条路。

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root==nil{
        return false
    }
    var traversal func(root *TreeNode, sum int)bool
    traversal = func(root *TreeNode, sum int)bool{
        // fmt.Println(sum)
        if root.Left==nil&&root.Right==nil&&sum==targetSum{
            return true
        }
        // 叶子节点直接返回
        if root.Left==nil&&root.Right==nil{
            return false
        }
        if root.Left!=nil{
            if traversal(root.Left, sum+root.Left.Val){
                return true
            }
            // sum -= root.Left.Val
        }
        if root.Right!=nil{
            if traversal(root.Right, sum+root.Right.Val){
                return true
            }
            // sum -= root.Right.Val
        }
        return false
    }
    return traversal(root, root.Val)
}