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

2024-05-23
福建
本文字数：952 字
阅读完需：约 3 分钟

原题链接：

解题思路：

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

示例代码

/** * 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};