2023-03-19 力扣112 基础路径总和

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

// 指定数据结构
// function Tree(val, left, right) {
//   this.val = val === undefined ? 0 : val;
//   this.left = left === undefined ? null : left;
//   this.right = right === undefined ? null : right;
// }

// 第一种解法：递归
// 大问题转化为小问题
var hasPathSum1 = function (root, targetSum) {
  if (!root) {
    return 0;
  }
  if (targetSum == root.val && !root.left && !root.right) {
    return true;
  }
  return (
    hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val)
  );
};

// 第二种解法：深度优先
var hasPathSum2 = function (root, targetSum) {
  if (!root) {
    return false;
  }
  let result = false;
  function dfs(root, l) {
    if (!root) {
      return;
    }
    if (l == targetSum && !root.left && !root.right) {
      result = true;
    }
    if (root.left) {
      dfs(root.left, l + root.left.val);
    }
    if (root.right) {
      dfs(root.right, l + root.right.val);
    }
  }
  dfs(root, root.val);
  return result;
};

// 第三种解法：广度优先
var hasPathSum3 = function (root, targetSum) {
  if (!root) {
    return false;
  }
  const treeArray = [[root, root.val]];
  while (treeArray.length) {
    const [subTree, sum] = treeArray.shift()
    if (sum == targetSum && !subTree.left && !subTree.right) {
      return true;
    }
    if (subTree.left) {
      treeArray.push([subTree.left, sum + subTree.left.val]);
    }
    if (subTree.right) {
      treeArray.push([subTree.right, sum + subTree.right.val]);
    }
  }
  return false;
};