112. 路径总和

题目描述

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

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
- (1 –> 2): 和为 3
- (1 –> 3): 和为 4
- 不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [ ], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

解法一：递归

错误代码 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


/**
 * 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
    }
    var dfs func(root *TreeNode, targetSum int) bool
    dfs = func(root *TreeNode, targetSum int) bool {
        if root == nil {
            if targetSum == 0 {
                return true
            }
            return false
        }
        targetSum -= root.Val
        left :=dfs(root.Left, targetSum)
        if left {
            return true
        }
        right :=dfs(root.Right, targetSum)
        return right
    }
    return dfs(root, targetSum)
}

不能通过如下测试用例

输入：root = [1, 2]；targetSum = 1
输出：true
预期结果：false

正确代码 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


/**
 * 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 {
        targetSum -= root.Val
        if root.Left == nil && root.Right == nil {
            if targetSum == 0 {
                return true
            }
            return false
        }
        left := hasPathSum(root.Left, targetSum)
        if left {
            return true
        }
        right := hasPathSum(root.Right, targetSum)
        return right
    }
    return false
}

官方题解如下，代码更加简洁

1
2
3
4
5
6
7
8
9


func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return sum == root.Val
    }
    return hasPathSum(root.Left, sum - root.Val) || hasPathSum(root.Right, sum - root.Val)
}