human
I am working on the file "03_BinaryTree_DivideConquer.ipynb".
The first task is:
Binary Tree Path Sum
Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target.
A valid path is from root node to any of the leaf nodes.
https://www.lintcode.com/en/problem/binary-tree-path-sum/
https://leetcode.com/problems/path-sum-ii/#/description
Can you write Python code for it?
assistant
#Here is Python code to find all paths that sum of the nodes in the path equals to a given number target.

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    # @param {TreeNode} root the root of binary tree
    # @param {int} target an integer
    # @return {int[][]} all valid paths
    def binaryTreePathSum(self, root, target):
        # Write your code here
        
        if root is None:
            return []
            
        if root.left is None and root.right is None and root.val == target:
            return [[root.val]]
        
        left = self.binaryTreePathSum(root.left, target - root.val)
        right = self.binaryTreePathSum(root.right, target - root.val)
        
        paths = []
        for p in left:
            paths += [[root.val] + p]
        for p in right:
            paths += [[root.val] + p]
        return paths