LeetCode题解：112. 路径总和，BFS，JavaScript，详细注释

原题链接：

112. 路径总和

解题思路：

1. 开始此题前，请先完成102. 二叉树的层序遍历的BFS解法
2. 计算思路
   1. 如果求根节点到叶子节点的路径上的节点值之和，假设共有3个节点，那么写成计算式是val1 + val2 + val3 = sum
   2. 那么将计算式转换就可以得到val3 = sum - val1 - val2
   3. 也就是说，问题可以从求和转换为，每向下查找一层节点，就将求和减去当前节点的值，最后只要判断叶子节点的值val3，是否和最后sum - val1 - val2相等即可
3. 也就是说我们只要在每一层搜索时，缓存targetSum减去从当前节点到根节点的值的结果。
4. 之后在搜索到叶子节点时，就可以直接对比叶子节点的值，与缓存结果是否相等即可

示例代码

/**
 * 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 {boolean}
 */
var hasPathSum = function(root, targetSum) {
  // 使用队列进行广度优先搜索
  const queue = new Queue();
  // 如果root不为空，则入队
  root && queue.enqueue({ node: root, val: targetSum })

  // 不断循环，知道队列为空，表示完成搜索
  while (queue.size()) {
    // 获取当前层的节点数量
    let size = queue.size()

    // 将当前层的节点全部依次出队
    while (size--) {
      // 队列的每个元素缓存了当前节点，以及targetSum减去之前所有节点值的差
      const { node, val } = queue.dequeue()

      // 如果当前节点是叶子节点
      if (!node.left && !node.right) {
        // 如果当前节点的值，等于val，表示路径上的节点值之和等于targetSum
        if (node.val === val) {
          return true
        }
      }

      // 将当前节点的子节点都入队，并缓存targetSum减去点前节点到根节点所有值之差
      node.left && queue.enqueue({ node: node.left, val: val - node.val })
      node.right && queue.enqueue({ node: node.right, val: val - node.val })
    }
  }

  // 如果遍历所有路径后，都没有找到符合条件路径，就返回false
  return false
};