112.路径总和1

# 给你二叉树的根节点 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 
#  
#  Related Topics 树 深度优先搜索 二叉树 

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        def backStack(tem: TreeNode, target):
            if not tem:
                return False
            # 叶子节点匹配返回True
            if not tem.left and not tem.right:
                if tem.val == target:
                    return True
            return backStack(tem.left, target - tem.val) or backStack(tem.right, target - tem.val)

        return backStack(root, targetSum)

113.路径总和2

# 给你二叉树的根节点 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 
#  
#  
#  
#  Related Topics 树 深度优先搜索 回溯 二叉树 

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ret = []
        tem = []

        def backStack(root1: Optional[TreeNode], tar):
            if not root1:
                return
            # 找到叶子节点
            if not root1.left and not root1.right:
                if root1.val == tar:
                    tem.append(root1.val)
                    ret.append(tem[:])
                    tem.pop()
                else:
                    return
            # 回溯
            tem.append(root1.val)
            backStack(root1.left, tar - root1.val)
            backStack(root1.right, tar - root1.val)
            tem.pop()

        backStack(root, targetSum)
        return ret