路径总和

LeetCode 112：DFS 到叶子，累加路径和判断。

#resource / algorithm #type / howto #status / evergreen #source / leetcode #ds / tree #algo / dfs #algo / recursion

[!info] related notes 算法面试题型 MOC 二叉树基础

路径总和

题目

112. 路径总和 - 力扣（LeetCode）

思路

DFS：沿根到叶子的路径向下走，维护剩余和 targetSum。

到叶子时，判断 targetSum == node.val
否则递归到左右子树，传入 targetSum - node.val

代码（JavaScript）

var hasPathSum = function(root, targetSum) {
  if (root === null) return false;
  if (root.left === null && root.right === null) {
    return targetSum === root.val;
  }
  const rest = targetSum - root.val;
  return hasPathSum(root.left, rest) || hasPathSum(root.right, rest);
};