【算法题】路径总和 - Javascript版本

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

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

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

输出：true

解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

使用 BFS 迭代

维护一个队列记录当前节点，并根据当前节点搜索下一层

维护一个队列记录路径和 temp，并时刻更新（将下一层的节点值计算进去，并时刻判断是否为叶子节点，如果是叶子节点则将 temp 与targetSum进行比较）

跟 层序遍历 的代码很像

var hasPathSum = function (root, targetSum) {
  if (!root) {
    return false;
  }

  // BFS法 创建两个数组 一个记录所有节点 一个记录路径和
  const queue = [];
  const res = [];
  queue.push(root);
  res.push(root.val);

  // 进入BFS

  while (queue.length) {
    const top = queue.pop();
    const temp = res.pop();

    // 如果遍历到叶子节点处时 路径和=targetSum 则返回true
    if (top.left === null && top.right === null) {
      if (temp === targetSum) return true;
    }

    // 如层序遍历一般更新queue与路径和数组
    if (top.left) {
      queue.push(top.left);
      res.push(temp + top.left.val);
    }

    if (top.right) {
      queue.push(top.right);
      res.push(temp + top.right.val);
    }
  }

  return false;
};

使用递归，DFS

与广度优先使用计算路径和的思路反了过来

深搜使用的思想是，每层计算都进行 targetSum - root.val 如果到叶子节点时 targetSum === root.val 说明路径和符合要求了

var hasPathSum = function (root, targetSum) {
  if (root === null) {
    return false;
  }
  // 搜到叶子节点，则判断当前节点值是否等于目标值
  if (root.left === null && root.right === null) {
    return root.val === targetSum;
  }
  // 还没搜到叶子节点，则进行 目标值-当前节点值，并继续往下搜
  return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
};

原题地址：https://leetcode-cn.com/problems/path-sum