【leetcode】112. Path sum - 113 Path sum II

For details, please refer to 112. The sum of the paths

For details, please refer to 113. The sum of the paths II

112. The sum of the paths

Their thinking ：

• The first sequence traversal , If recursive root It's empty , Just go back to False Indicates that there is no and in this path TargetSum
• If the left and right subtrees are empty , And the current node is equal to targetSum, Just go back to True
• Then recursive left and right subtrees , See if the left and right subtrees can be matched

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 #  No, root, I just can't find 
        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. The sum of the paths II

Their thinking ：

• Traversal by preorder
• The current node is the leaf node , And the value of the current node == targetsum, Save this path
• If there is a left subtree, go to the left subtree , The left and right subtrees have been traversed , Will path Current node in pop, For example, the left node has been found , Output the left node path, Right node in 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