手撕：树中的路径之和等于target（包括从根节点开始到叶子结点，从根节点开始的任意路径，任意节点开始的任意路径）

// 根节点开始到叶子结点
const targetPath = (root, target) => {

    if(!root) return false

    const dfs = (root, curSum) => {

        if (!root) {
            return false;
        }

        if(!root.left && !root.right){
            return root.val === target
        }

        return dfs(root.left, curSum - root.val) || dfs(root.right, curSum - root.val)
    }

    return dfs(root, target);
}

const targetPath = (root, target) => {

    if(!root) return []

    let path = [];
    let result = [];
    const dfs = (root, curSum) => {

        if (!root) {
            return false;
        }

        if(curSum===0 && !root.left && !root.right){
            result = path.slice();
            return;
        }

        path.push(root.val)
        
        if(root.left) dfs(root.left, curSum - root.val)
        if(root.right) dfs(root.right, curSum - root.val)

        path.pop();
    }

    return dfs(root, target);
}

// 从根节点开始的任意路径
const tatgetPath = (root, target) => {
    
    let allPaths = [];

    let path = [];

    const dfs = (node, current) => {
        if(!node){
            return;
        }
        path.push(node.val);

        if(current-node.val === 0){
            allPaths.push(path.slice());
            // 这里不return
        }

        if(node.left) dfs(node.left, current - node.val);
        if(node.right) dfs(node.right, current - node.val);

        path.pop();
    }

    dfs(root, target);

    return allPaths;
}

// 任意节点开始的任意路径
// 树状前缀和