1. 112 路径总和

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/path-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

该题的意思是，从根节点出发到最叶子节点的路径和，是否为目标值

解答

思路：计算出从根到最叶子节点的路径和
有几个问题点：

1. 如何判断该节点是否为最叶子节点：!node.left && !node.right
2. 如何遍历路径
   1. 分析这是层级遍历
   2. 使用 迭代 或者 递归

3. 如何存储路径和，把之前计算值暂存到节点上 node.sum

   迭代

   var hasPathSum = function(root, targetSum) {
    let stack = [root];
    if (!root) {
        return false;
    }
    while (stack.length) {
        for (let i = 0, len = stack.length; i < len; i++) {
            const node = stack.shift();
            const prevSum = node.prevSum || 0;
            let tempSum = prevSum;
            if (node.val) {
                tempSum += node.val;
            }
            if (node.left) {
                node.left.prevSum = tempSum
                stack.push(node.left);
            }
            if (node.right) {
                node.right.prevSum = tempSum;
                stack.push(node.right);
            }
            if (!node.left && !node.right) {
                console.log('tempSum:', tempSum, targetSum)
                if (tempSum === targetSum) {
                    return true
                }
            }
        }
    }
    return false
   };

   递归

   var hasPathSum = function(root, targetSum) {
    if (!root) return false
   
    const sums = [];
    function caculate (node) {
        if (!node.left && !node.right) {
            sums.push(node.sum);
        }
        if (node.left) {
            node.left.sum = node.sum + node.left.val;
            caculate(node.left);
        }
        if (node.right) {
            node.right.sum = node.sum + node.right.val;
            caculate(node.right);
        }
    }
   
    root.sum = root.val;
    caculate(root);
   
    console.log('sums:', sums)
   
    return sums.includes(targetSum);
   };
   

   优化

   不需要存储计算和到节点上，把当前节点走到的路径和从目标值减去，走到最叶子节点，哪个为 0 则说明是目标路径

   var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    function caculate (node, cnt) {
        if (!node.left && !node.right) {
            return cnt === 0;
        } else {
            if (node.left && caculate(node.left, cnt - node.left.val)) {
                return true;
            }
            if (node.right && caculate(node.right, cnt - node.right.val)) {
                return true;
            }
        }
   
        return false;
    }
   
    return caculate(root, targetSum - root.val);
   };