路径和篇 ​

const hasPathSum = (root, tarSum) => {
  if (!root) return false
  const dfs = (node, curSum) => {
    if (!node) return false
    if (!node.left && !node.right) return curSum === tarSum
    return dfs(node.left, curSum + node.left.val)
      || dfs(node.right, curSum + node.right.val)
  }
  return dfs(root, root.val)
}

const pathSum = (root, tarSum) => {
  if (!root) return []
  const ret = []
  const dfs = (node, path, curSum) => {
    if (!node.left && !node.right && curSum === tarSum) return ret.push(path)
    node.left && dfs(node.left, [...path, node.left.val], curSum + node.left.val)
    node.right && dfs(node.right, [...path, node.right.val], curSum + node.right.val)
  }
  dfs(root, [root.val], root.val)
  return ret
}

const pathSum = (root, tarSum) => {
  let ret = 0
  const map = new Map()
  const dfs = (node, preSum) => {
    if (!node) return 0
    map.set(preSum, (map.get(preSum) || 0) + 1)
    const curSum = preSum + node.val
    ret += map.get(curSum - tarSum) || 0
    dfs(node.left, curSum)
    dfs(node.right, curSum)
    // 避免重复计算
    map.set(preSum, map.get(preSum) - 1)
  }
  dfs(root, 0)
  return ret
}

const maxPathSum = root => {
  let max = -Infinity
  const dfs = node => {
    if (!node) return 0
    // 左树最大贡献（小于0，就不贡献）
    const maxL = Math.max(dfs(node.left), 0)
    // 右树最大贡献
    const maxR = Math.max(dfs(node.right), 0)
    max = Math.max(max, maxL + node.val + maxR)
    return node.val + Math.max(maxL, maxR)
  }
  dfs(root)
  return max
}

const longestUnivaluePath = root => {
  let max = 0
  const dfs = node => {
    if (!node) return 0
    let maxL = dfs(node.left)
    let maxR = dfs(node.right)
    maxL = node.left && node.left.val === node.val ? ++maxL : 0
    maxR = node.right && node.right.val === node.val ? ++maxR : 0
    max = Math.max(max, maxL + maxR)
    return Math.max(maxL, maxR)
  }
  dfs(root)
  return max
}

const sumNumbers = root => {
  let sum = 0
  const dfs = (node, num) => {
    if (!node) return 0
    if (!node.left && !node.right) {
      return sum += num
    }
    const left = node.left && dfs(node.left, num * 10 + node.left.val)
    const right = node.right && dfs(node.right, num * 10 + node.right.val)
    return left + right
  }
  dfs(root, root.val)
  return sum
}