112. Path Sum

/**
 * 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) {
  // 定义内部递归函数，处理遍历和回溯逻辑
  function traversal(cur, count) {
    // 终止条件1：遇到叶子节点且剩余路径和为0，找到符合条件的路径
    if (cur.left === null && cur.right === null && count === 0) {
      return true
    }
    // 终止条件2：遇到叶子节点但剩余路径和不为0，该路径不符合
    if (cur.left === null && cur.right === null) {
      return false
    }

    // 处理左子树
    if (cur.left !== null) {
      count -= cur.left.val // 扣减左子节点值
      if (traversal(cur.left, count)) {
        // 递归左子树
        return true
      }
      count += cur.left.val // 回溯，恢复count值
    }

    // 处理右子树
    if (cur.right !== null) {
      count -= cur.right.val // 扣减右子节点值
      if (traversal(cur.right, count)) {
        // 递归右子树
        return true
      }
      count += cur.right.val // 回溯，恢复count值
    }

    // 左右子树都无符合条件的路径
    return false
  }

  // 边界条件：根节点为空，直接返回false
  if (root === null) {
    return false
  }
  // 初始调用递归函数，初始剩余值为 目标值 - 根节点值
  return traversal(root, targetSum - root.val)
}

/**
 * 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}
 */
function hasPathSum(root, sum) {
  // 1. 空节点直接返回false
  if (root === null) return false

  // 2. 到达叶子节点时，判断当前节点值是否等于剩余目标和
  if (root.left === null && root.right === null && sum === root.val) {
    return true
  }

  // 3. 递归遍历左右子树，目标和减去当前节点值
  const remainingSum = sum - root.val
  return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum)
}