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

题目描述:

给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回 true；否则，返回false。叶子节点是指没有子节点的节点。

思来想去，还是递归简单。而递归函数的编写，关键在于三点:

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以上内容感谢作者代码随想录的文章

解题思路:

1. 递归
2. 递归的第一条件之确定函数返回值以及参数: 结果为true或者false，因为递归调用。那参数肯定是节点以及值
3. 递归之第二条件之确定终止条件：返回真或者假即为终止
4. 递归第三条件之单层递归逻辑: 该层只判断节点是否为空，以及节点值是否等于目标值。不相等，继续调用递归函数，但参数为当前节点的左节点与右节点，目标值为原目标值减去当前节点值本身。

golang示例代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    // 用递归写起来简单，迭代估计很麻烦
    if root == nil {
        return false
    }
    if root.Val == targetSum && root.Left == nil && root.Right == nil {
        return true
    }
    return hasPathSum(root.Left, targetSum - root.Val) || hasPathSum(root.Right, targetSum - root.Val)
}

文章目录