路径之和

LeetCode112. 路径总和

题目描述

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

思路

1. 确定递归函数的参数和返回类型
   • 参数：传入根节点、计数器记录路径和
   • 递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
     • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值
     • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值
     • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回（本题的情况）
2. 确定终止条件
   • 用计数器统计这一条路径的和
   • 不要去累加然后判断是否等于目标和，那样代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值
   • 如果最后count == 0，同时到了叶子节点的话，说明找到了目标和
   • 如果遍历到了叶子节点，count不为0，就是没找到
3. 确定单层递归的逻辑
   • 因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了
   • 递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func hasPathSum(root *TreeNode, targetSum int) bool {
    // 若传入空节点,则返回false
    if root == nil {
        return false
    }
    targetSum -= root.Val // 将targetSum在遍历每层的时候都减去本层节点的值
    if root.Left == nil && root.Right == nil && targetSum == 0 {
        // 如果剩余的targetSum为0, 则正好就是符合的结果
        return true
    }
    // 否则递归找
    return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum) 
}

Link

GitHub