112. 路径总和

112. 路径总和 - 力扣（Leetcode）

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

沿用那个的代码，当然是能过：

但是下边这个代码也能过！根本不用判断是否只有一个子树的时候。二者逻辑是有本质区别的，你们自己捋一捋。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == targetSum
        
        return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)

1. 首先，该函数 hasPathSum 接受两个参数，一个是二叉树的根节点 root，另一个是目标和 targetSum。

2. 如果 root 为空，则直接返回 False，表示此时不存在满足条件的路径。

3. 如果 root 既没有左子树也没有右子树，那么只有在 root 的值等于 targetSum 时才会返回 True，因为这意味着路径的和就是 targetSum。

4. 如果 root 有左子树或右子树，则需要递归调用 hasPathSum 函数来检查其左右子树是否存在满足条件的路径。具体地，检查从 root 的左子树或右子树出发，能否找到一条和为 targetSum-root.val 的路径。

5. 如果左子树和右子树中至少有一棵子树存在满足条件的路径，则该函数返回 True，否则返回 False。

总体来说，该函数使用递归算法实现，递归地检查从根节点开始，是否存在和为 targetSum 的路径。如果存在，则返回 True，否则返回 False。

为了下一题铺垫，我们把代码写成这样：

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

        def dfs(root,s):
            if not root:
                return False
            if not root.left and not root.right:
                return s == root.val
            return dfs(root.left,s-root.val) or dfs(root.right,s-root.val)
        
        return dfs(root,targetSum)

113. 路径总和 II

113. 路径总和 II - 力扣（Leetcode）

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

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

 

示例 1：

输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出： [[5,4,11,2],[5,8,4,5]]

示例 2：

输入： root = [1,2,3], targetSum = 5
输出： []

示例 3：

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

 

提示：

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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        res = []
        path = []
        
        def dfs(root, targetSum):
            if not root:
                return
            path.append(root.val)
            if not root.left and not root.right and targetSum == root.val:
                ret.append(path[:])
            dfs(root.left, targetSum - root.val)
            dfs(root.right, targetSum - root.val)
            path.pop()
        
        dfs(root, targetSum)
        return res

方法首先定义了两个空列表：res 和 path。res 用于存储最终结果，而 path 用于存储当前遍历的路径。

接下来，方法定义了一个名为 dfs 的嵌套函数，该函数接受两个参数：root 和 targetSum。该函数使用深度优先搜索算法遍历二叉树。

如果当前节点 root 为空，则函数返回。否则，将当前节点的值添加到 path 列表中，并对左右子节点分别调用 dfs 函数。

如果当前节点是叶子节点且其值等于剩余的目标和，则将当前路径的副本添加到结果列表 res 中。

最后，在退出当前节点之前，从 path 列表中弹出当前节点的值。

在 pathSum 方法的主体中，调用了一次 dfs 函数，并返回结果列表 res。

这段代码的时间复杂度为 O(n2)O(n^2)O(n2)，其中 n 是二叉树中节点的数量。这是因为在最坏情况下，二叉树可能是一条链，每次调用 dfs 函数时都需要遍历整个链。

空间复杂度为 O(n)O(n)O(n)，其中 n 是二叉树中节点的数量。这是因为需要使用递归栈和 `path

129. 求根节点到叶节点数字之和

129. 求根节点到叶节点数字之和 - 力扣（Leetcode）

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

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

 

示例 1：

输入： root = [1,2,3]
输出： 25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入： root = [4,9,0,5,1]
输出： 1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

 

提示：

• 树中节点的数目在范围 [1, 1000] 内
• 0 <= Node.val <= 9
• 树的深度不超过 10

这题没啥好说的，代码完全照搬上一题：

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        res = 0
        num = 0
        
        def dfs(root: TreeNode):
            if not root:
                return
            nonlocal num,res
            num = num*10 + root.val
            dfs(root.left)
            dfs(root.right)
            if not root.left and not root.right:
                res += num
            num //= 10
        
        dfs(root)
        
        return res

首先定义了两个变量：res 和 num。res 用于存储最终结果，而 num 用于存储当前遍历的数字。

接下来，方法定义了一个名为 dfs 的嵌套函数，该函数接受一个参数：root。该函数使用深度优先搜索算法遍历二叉树。

如果当前节点 root 为空，则函数返回。否则，将当前节点的值添加到 num 中，并对左右子节点分别调用 dfs 函数。

如果当前节点是叶子节点，则将当前数字累加到结果变量 res 中。

最后，在退出当前节点之前，从 num 中删除当前节点的值。

在 sumNumbers 方法的主体中，调用了一次 dfs 函数，并返回结果变量 res。

这段代码的时间复杂度为 O(n)，其中 n 是二叉树中节点的数量。这是因为需要遍历整棵二叉树来计算所有从根到叶子的数字之和。

空间复杂度为 O(h)，其中 h 是二叉树的高度。这是因为需要使用递归栈来存储遍历过程中的信息，递归栈的最大深度等于二叉树的高度。