337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

3
        ↙   ↘
      2         3
        ↘        ↘
          3         1

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

3
        ↙   ↘
      4         5
   ↙   ↘        ↘
 1        3         1

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

• Constraints:
  • The number of nodes in the tree is in the range [1, 104].
  • 0 <= Node.val <= 104

Analyze

根据题目可知，可盗取最大值 f(root) = Math.max(root.val + f(root 的孙节点), f(root 的子节点))，顺势使用递归解题：

/**
 * 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
 * @return {number}
 */
var rob = function(root) {
  if (!root) return 0
  return Math.max(
    root.val
    + (root.left && root.left.left ? rob(root.left.left) : 0)
    + (root.left && root.left.right ? rob(root.left.right) : 0)
    + (root.right && root.right.left ? rob(root.right.left) : 0)
    + (root.right && root.right.right ? rob(root.right.right) : 0),
    (root.left ? rob(root.left) : 0)
    + (root.right ? rob(root.right) : 0)
  )
}

此时解题超时，接着进行优化。

在递归基础上加上缓存

/**
 * 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
 * @return {number}
 */
var rob = function(root) {
  const cache = new Map()
  return robRecursive(root, cache)
}

function robRecursive(node, cache) {
  if (!node) return 0
  if (cache.get(node)) return cache.get(node)
  const index = cache.index = cache.index + 1
  const curNodeMax = Math.max(
    node.val
    + (node.left && node.left.left ? robRecursive(node.left.left, cache) : 0)
    + (node.left && node.left.right ? robRecursive(node.left.right, cache) : 0)
    + (node.right && node.right.left ? robRecursive(node.right.left, cache) : 0)
    + (node.right && node.right.right ? robRecursive(node.right.right, cache) : 0),
    (node.left ? robRecursive(node.left, cache) : 0)
    + (node.right ? robRecursive(node.right, cache) : 0)
  )
  cache.set(node, curNodeMax)

  return curNodeMax
}

技巧小结：使用 map 代替 object 来记录缓存，参考 http://muyunyun.cn/blog/c1nhctpd

基于树状结构的动态规划

前置知识点：在 Tree 数据结构中，使用后序遍历可以达到动态规划中至底向上遍历的效果。

当前节点可盗取最大值为 Max{f(node), g(node)}，其中 f(node) 表示当前 node 节点被选中时的最大值，g(node) 表示当前节点非选中时的最大值。

• 当 node 节点为选中时，node 相邻子节点均不可被选中，此时 f(node) = g(l) + g(r);
• 当 node 节点为非选中时，g(node) 为左侧子节点选中与非选中态下的最大值与右侧子节点选中与非选中态下的最大值之和，即 g(node) = Max{f(l), g(l)} + Max{f(r), g(r)};

/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
  const [selected, notSelected] = postRecursive(root)
  return Math.max(selected, notSelected)
}

function postRecursive(node) {
  if (!node) return [0, 0]

  const l = postRecursive(node.left)
  const r = postRecursive(node.right)

  const selected = node.val + l[1] + r[1]
  const notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1])

  return [selected, notSelected]
}