跟随carl代码随想录刷题
语言：python

如果需要搜索整棵二叉树，那么递归函数就不要返回值，如果要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。——代码随想录

112. 路径总和

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

题目分析

完整代码如下

# 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:
        def isornot(root, targetSum):
            if (not root.left) and (not root.right):
                if targetSum == 0:
                    return True
                else:
                    return False
            if root.left:
                targetSum -= root.left.val
                if isornot(root.left, targetSum):
                    return True
                targetSum += root.left.val  # 如果执行到这一步，说明上面哪条路径并不符合，因此需要把减掉的值加回来
            if root.right:
                targetSum -= root.right.val
                if isornot(root.right, targetSum):
                    return True
                targetSum += root.right.val
            return False
        
        if root == None:
            return False
        else:
            return isornot(root, targetSum - root.val)         

113. 路径总和 II

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

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

题目分析

代码运行流程图：

完整代码如下

# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        def traversal(cur, remain):
            if not cur.left and not cur.right:
                if remain == 0:
                    result.append(path[:])  # 这一步很关键`path[:]`，不是`path`
                return

            if cur.left:
                path.append(cur.left.val)
                traversal(cur.left, remain - cur.left.val)
                path.pop()  # 如果走到这一步，说明上述路径不符合要求，所以要回溯

            if cur.right:
                path.append(cur.right.val)
                traversal(cur.right, remain - cur.right.val)
                path.pop()  # 回溯


        result , path = [], []
        if not root:
            return []
        path.append(root.val)
        traversal(root, targetSum - root.val)
        return result