113.路径总和2

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
    let res = []

    // 深度优先遍历
    function deepOrder(root, target, pathNodes) {
        // 注意需要浅拷贝，否则同一个数组内存地址相同，最后pathNodes是全部节点
        let nodes = Array.from(pathNodes || [])

        if (!root) {
            return
        }
        // 路径上的节点
        nodes.push(root.val)

        // 找到与差值相同的叶子节点
        if (root.left === null && root.right === null && root.val === target) {
            res.push(nodes)
            return
        }

        // 继续往下找差值
        deepOrder(root.left, target - root.val, nodes)
        deepOrder(root.right, target - root.val, nodes)
    }

    deepOrder(root, targetSum)
    return res
};

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function (root, targetSum) {
    if (!root) {
        return []
    }
    // 使用广度优先遍历+哈希表记录每个节点的父节点方便回溯
    let queue = [] // 每一层的节点
    queue.push(root)

    let sumQueue = [] // 路径sum队列
    sumQueue.push(root.val) // 刚开始经过root的路径和

    let pathLastNodes = [] // 每一条符合targetSum的最后一个节点集合

    let map = new Map() // key是节点，value是父节点
    map.set(root, null) // 根节点的父节点为null

    while (queue.length) {
        let len = queue.length // 当前层的节点数
        for (let i = 0; i < len; i++) {
            let node = queue.shift() // 当前节点
            let sum = sumQueue.shift() // 当前节点的路径和
            if (node.left === null && node.right === null && sum === targetSum) {
                pathLastNodes.push(node)
            }

            if (node.left) {
                queue.push(node.left)
                map.set(node.left, node) // 记录父节点
                sumQueue.push(sum + node.left.val) // 访问左节点后的路径和
            }
            if (node.right) {
                queue.push(node.right)
                map.set(node.right, node) // 记录父节点
                sumQueue.push(sum + node.right.val) // 访问右节点的路径和
            }
        }
    }

    // console.log(pathLastNodes)
    // map记录了每个节点的父节点，我们可以进行回溯，找出从叶子节点到根节点的整个path
    let res = []
    for (let i = 0; i < pathLastNodes.length; i++) {
        let path = []
        let node = pathLastNodes[i]
        // 根节点的父节点是null，遍历到根节点停止循环
        while (node !== null) {
            path.unshift(node.val) // 从前面插入
            node = map.get(node)
        }
        res.push(path)
    }

    return res
}