112 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

题解

这题的关键点在于是从根节点到叶子节点，所以递归的时候只要递归到叶子节点，不要递归到空节点。 其次我们可以用累减来少记录当前总和。

var hasPathSum = function (root, targetSum) {
    var hasPathSumAfterOrder = function (root, targetSum) {
        //只递归到叶子节点，停止
        if (root && !root.left && !root.right) {
            //如果叶子节点等于目标值，返回true
            if (targetSum === root.val) {
                return true
            } else {
                return false
            }
        }

        //如果有左叶子，递归判断， 总和减少
        if (root.left) {
            if(hasPathSumAfterOrder(root.left, targetSum - root.val)) {
                return true
            }
        }
        //如果有右叶子，递归判断， 总和减少
        if (root.right) {
            if(hasPathSumAfterOrder(root.right, targetSum - root.val)) {
                return true
            }
        }
        return false
    }
    if (!root) {
        return false
    }
    return hasPathSumAfterOrder(root, targetSum)
};

非递归遍历

非递归的回溯算法，在二叉树所有路径中没有提及，这里说明一下，需要同时存当前节点和当前的路径也好，累加值也好。

var hasPathSum = function (root, targetSum) {
    const stack = []
    if (!root) {
        return false
    }
    //同时存栈和栈上经过的路径和
    stack.push([root, root.val])
    while (stack.length) {
        const currentNode = stack.pop()
        const current = currentNode[0]
        const value = currentNode[1]
        //console.log('current node', current, 'current value', value)
        if(!current.left  && !current.right && value === targetSum) {
            return true
        }
        if (current.right) {
            stack.push([current.right, value + current.right.val])
        }
        if (current.left) {
            stack.push([current.left, value + current.left.val])
        }
    }
    return false
};