🌲二叉树看递归问题（下）
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
沿用那个的代码，当然是能过：
但是下边这个代码也能过！根本不用判断是否只有一个子树的时候。二者逻辑是有本质区别的，你们自己捋一捋。
# 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)
-
首先，该函数
hasPathSum接受两个参数，一个是二叉树的根节点root，另一个是目标和targetSum。 -
如果
root为空，则直接返回False，表示此时不存在满足条件的路径。 -
如果
root既没有左子树也没有右子树，那么只有在root的值等于targetSum时才会返回True，因为这意味着路径的和就是targetSum。 -
如果
root有左子树或右子树，则需要递归调用hasPathSum函数来检查其左右子树是否存在满足条件的路径。具体地，检查从root的左子树或右子树出发，能否找到一条和为targetSum-root.val的路径。 -
如果左子树和右子树中至少有一棵子树存在满足条件的路径，则该函数返回
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
给你二叉树的根节点 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 是二叉树的高度。这是因为需要使用递归栈来存储遍历过程中的信息，递归栈的最大深度等于二叉树的高度。