题目

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)
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:459605 人次
ICP备案号: 辽ICP备20003309号