112.路径总和

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 {boolean}
 */
var hasPathSum = function (root, targetSum) {
    if (!root) {
        return false
    }
    // 层序遍历+记录sum队列,两个队列长度一样
    let sumQueue = [] // 每经过一个节点时sum的值
    let queue = []
    queue.push(root)
    sumQueue.push(root.val)
    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) {
                if (sum === targetSum) {
                    return true
                }
            }

            if (node.left) {
                queue.push(node.left)
                sumQueue.push(sum + node.left.val)
            }
            if (node.right) {
                queue.push(node.right)
                sumQueue.push(sum + node.right.val)
            }
        }
    }
    return false
};

let root = new TreeNode(1)
// root.left = new TreeNode(2)
console.log(hasPathSum(root, 1));

// 递归找差值，往下找 newTargetSum = targetSum - node.val
var hasPathSum = function (root, targetSum) {
    if (root === null) {
        return false
    }
    if (root.left == null && root.right === null && root.val === targetSum) {
        return true
    }
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val)
}