112. 路径总和-技术圈

给你二叉树的根节点 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

题目解析

题目解答

方法：回溯法思路：    step 1：判空    step 2：回溯

方法：递归思路：    step 1：如果 空节点，return False    step 2：走到 叶子节点，而且 刚好 路径和 等于 sum    step 3：向 left 和 right 递归

代码展示

# 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:        '''            方法：回溯法            思路：                step 1：判空                step 2：回溯        '''        # step 1：判空        if not root: return False         # step 2：回溯        return self.dfs(root,sum)
    def dfs(self,root,target):        '''            方法：回溯法            思路：                step 1：判空                step 2：当叶子节点的值 等于 当前 target 时，满足条件                step 3：初实化                step 4: 向 left 和 right 沿伸                 step 5：测回        '''        # step 1：判空        if not root: return False         # step 2：当叶子节点的值 等于 当前 target 时，满足条件        if target==root.val and not root.left and not root.right:            return True         # step 3：初实化        # step 4: 向 left 和 right 沿伸         if root.left:            left = self.dfs(root.left,target-root.val)            # left 为 True,剪枝            if left:                return True        if root.right:            right = self.dfs(root.right,target-root.val)            # right 为 True,剪枝            if right:                return True        # step 5：测回        return False
    def hasPathSum1(self, root: TreeNode, sum: int) -> bool:        '''            方法：递归            思路：                step 1：如果 空节点，return False                step 2：走到 叶子节点，而且 刚好 路径和 等于 sum                step 3：向 left 和 right 递归        '''        # step 1：如果 空节点，return False        if not root:            return False        # step 2：走到 叶子节点，而且 刚好 路径和 等于 sum        if not root.left and not root.right and sum==root.val:            return True           # step 3：向 left 和 right 递归        left = self.hasPathSum(root.left,sum-root.val)        right = self.hasPathSum(root.right,sum-root.val)        return left or right

复杂度计算

运行结果