【leetcode】112. 路径总和 - 113. 路径总和 II

题目详见112. 路径总和

题目详见 113. 路径总和 II

112.路径总和

解题思路：

• 先序遍历，如果递归中root 为空，就返回False表示该路径下没有和为TargetSum
• 如果左右子树都为空，并且当前节点等于targetSum，就返回True
• 然后递归左右子树，看左右子树是否能被匹配到

talk is cheap ， show me the code

# 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 # 没有root，就是没有找到
        if not root.left and not root.right and root.val == targetSum:
            return True
        return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right,targetSum-root.val)

113.路径总和 II

解题思路：

• 用先序遍历
• 当前节点为叶子节点，并且当前节点的值== targetsum，则将此条路径保存
• 如果有左子树则去左子树上找，左右子树都遍历完了，则将path中当前节点pop，例如左节点找完了，将左节点出path，右节点入path

Talk is cheap， show me the code

# 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]]:
        if not root:
            return []
        path = []
        result = []
        def dfs(root,targetSum):
            if not root:
                return 
            path.append(root.val)
            targetSum -= root.val
            if not root.left and not root.right and targetSum==0:
                result.append(path[:])
            if root.left:
                dfs(root.left,targetSum)
            if root.right:
                dfs(root.right,targetSum)
            path.pop()
        dfs(root,targetSum)
        return result