原文链接: https://leetcode-cn.com/problems/path-sum

英文原文

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

 

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

中文题目

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

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

 

示例 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

示例 3：

输入：root = [1,2], targetSum = 0
输出：false

 

提示：

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

通过代码

高赞题解

这个题要背下来！！

DFS

首先是 DFS 解法，该解法的想法是一直向下找到叶子节点，如果到叶子节点时sum == 0，说明找到了一条符合要求的路径。

我自己第一遍做的时候犯了一个错误，把递归函数写成了下面的解法：

def hasPathSum(self, root: TreeNode, sum: int) -> bool:
    if not root:
        return sum == 0
    return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

这种代码的错误在，没有判断 root 是否为叶子节点。比如 root 为空的话，题目的意思是要返回 False 的，而上面的代码会返回 sum == 0。又比如，对于测试用例 树为[1,2], sum = 0 时，上面的结果也会返回为 True，因为对于上述代码，只要左右任意一个孩子的为空时 sum == 0 就返回 True 。

当题目中提到了叶子节点时，正确的做法一定要同时判断节点的左右子树同时为空才是叶子节点。

Python 代码如下：

[]
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root: return False
        if not root.left and not root.right:
            return sum == root.val
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

[]
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }
        if(root.left == null && root.right == null){
            return root.val == sum;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
        
    }
}

回溯

这里的回溯指 利用 DFS 找出从根节点到叶子节点的所有路径，只要有任意一条路径的 和 等于 sum，就返回 True。

下面的代码并非是严格意义上的回溯法，因为没有重复利用 path 变量。

Python 代码如下：

[]
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root: return False
        res = []
        return self.dfs(root, sum, res, [root.val])
        
    def dfs(self, root, target, res, path):
        if not root: return False
        if sum(path) == target and not root.left and not root.right:
            return True
        left_flag, right_flag = False, False
        if root.left:
            left_flag = self.dfs(root.left, target, res, path + [root.left.val])
        if root.right:
            right_flag = self.dfs(root.right, target, res, path + [root.right.val])
        return left_flag or right_flag

BFS

BFS 使用 队列 保存遍历到每个节点时的路径和，如果该节点恰好是叶子节点，并且 路径和 正好等于 sum，说明找到了解。

Python 代码如下：

[]
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        que = collections.deque()
        que.append((root, root.val))
        while que:
            node, path = que.popleft()
            if not node.left and not node.right and path == sum:
                return True
            if node.left:
                que.append((node.left, path + node.left.val))
            if node.right:
                que.append((node.right, path + node.right.val))
        return False

栈

除了上面的 队列 解法以外，也可以使用 栈，同时保存节点和到这个节点的路径和。但是这个解法已经不是 BFS。因为会优先访问 后进来 的节点，导致会把根节点的右子树访问结束之后，才访问左子树。

可能会有朋友好奇很少见到这种写法，为什么代码可行？答案是：栈中同时保存了 (节点，路径和)，也就是说只要能把所有的节点访问一遍，那么就一定能找到正确的结果。无论是用 队列 还是 栈，都是一种 树的遍历 方式，只不过访问顺序有所有不同罢了。

Python 代码如下：

[]
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        stack = []
        stack.append((root, root.val))
        while stack:
            node, path = stack.pop()
            if not node.left and not node.right and path == sum:
                return True
            if node.left:
                stack.append((node.left, path + node.left.val))
            if node.right:
                stack.append((node.right, path + node.right.val))
        return False

统计信息

通过次数	提交次数	AC比率
294134	558725	52.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
路径总和 II	中等
二叉树中的最大路径和	困难
求根节点到叶节点数字之和	中等
路径总和 III	中等
路径总和 IV	中等