[!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);
};