124. 二叉树中的最大路径和

剑指 Offer II 051. 节点之和最大的路径

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。 给你一个二叉树的根节点 root ，返回其 最大路径和 。

答案

递归

var maxPathSum = function(root) {
  let maxSum = Number.MIN_SAFE_INTEGER
  const d = n => {
    if (n === null) return 0
    const leftSum = Math.max(0, d(n.left))
    const rightSum = Math.max(0, d(n.right))
    maxSum = Math.max(maxSum, n.val + leftSum + rightSum)
    return n.val + Math.max(leftSum, rightSum)
  }
  d(root)
  return maxSum
};

迭代

哈希表存左右节点的返回值

var maxPathSum = function(root) {
  const stack = [], h = new WeakMap
  let p = root, prev = null, maxSum = Number.MIN_SAFE_INTEGER
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      const leftSum = Math.max(0, h.get(n.left) || 0)
      const rightSum = Math.max(0, h.get(n.right) || 0) 
      maxSum = Math.max(maxSum, n.val + leftSum + rightSum)
      h.set(n, n.val + Math.max(leftSum, rightSum))
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return maxSum
};

968. 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。 计算监控树的所有节点所需的最小摄像头数量。

答案

字节跳动原题，动态规划三种状态，如上图所示：

• 节点安摄像头 a
• 节点安不安摄像头都行 b
• 节点不安摄像头 c

状态转换关系：当前节点 n 左节点 l 右节点 r

• 当前节点安：左节点不安，右节点不安
  • n_a = l_c + r_c + 1
• 当前节点安不安都行：当前节点的父节点安 / 左节点安，右节点安不安都行 / 右节点安，左节点安不安都行
  • n_b = min(n_a, l_a + r_b, r_a + l_b)
• 当前节点不安，当前节点的父节点安 / 左节点，右节点安不安都行
  • n_c = min(n_a, l_b + r_b)

递归

var minCameraCover = function(root) {
  const d = n => {
    if (n === null) return [Number.MAX_SAFE_INTEGER, 0, 0]
    const left = d(n.left)
    const right = d(n.right)
    const a = left[2] + right[2] + 1
    const b = Math.min(a, Math.min(left[0] + right[1], right[0] + left[1]))
    const c = Math.min(a, left[1] + right[1])
    return [a, b, c]
  }
  return d(root)[1]
};

迭代

哈希表存左右节点的返回值

var minCameraCover = function(root) {
  const stack = [], h = new WeakMap
  let prev = null, p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      const left = h.get(n.left) || [Number.MAX_SAFE_INTEGER, 0, 0]
      const right = h.get(n.right) || [Number.MAX_SAFE_INTEGER, 0, 0]
      const a = left[2] + right[2] + 1
      const b = Math.min(a, Math.min(left[0] + right[1], right[0] + left[1]))
      const c = Math.min(a, left[1] + right[1])
      h.set(n, [a, b, c])
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return h.get(root)[1]
};