[337] 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。

除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。

如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

输出: 7

解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

输出: 9

解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

这是打家劫舍系列的最后一道题了，解题思路同样可以参考198.打家劫舍与213.打家劫舍II。

这次题目的说明差点把我笑死，这么会编题不如出本书，就叫《论精通算法的程序员当了小偷会怎样行窃》【手动滑稽】

既然题目告诉你了需要规划的是一棵二叉树，那么就必定需要使用二叉树的遍历法则了，这里我们使用深度优先遍历来考虑。

还是与系列其他的题目相同，我们对于每一个节点都有取或者不取两种选择。

1. 如果取的话，下一家，即二叉树的两个直接子节点我们就不能取了，需要再向下一级，从隔代的4个孙子节点开始进行下一轮的遍历，将四个节点的最优解求和即为当前的最优解。
2. 如果不取的话，那么就能直接从两个子节点开始下一轮的遍历了，将两个节点的最优解求和即为当前的最优解。

依照这个思想，我们很快能写出递归解法。

var rob = function(root) {
  return dfs(root);

  function dfs(root) {
    if (!root) return 0;

    // 若决定抢这家，当前子节点就不考虑了，就直接去四个孙子节点再考虑了
    let rob = root.val;
    if (root.left) rob += dfs(root.left.left) + dfs(root.left.right);
    if (root.right) rob += dfs(root.right.left) + dfs(root.right.right);

    // 若决定不抢这家，就在子节点上继续考虑
    const giveup = dfs(root.left) + dfs(root.right);
    return Math.max(rob, giveup);
  }
};

这道题就算是被解决了。

但是问题也是很明显的，就是这样递归的复杂度实在是太高了，一个递归将会使用六个递归的结果，这样很容易被判超时，因此我们需要进行一些剪枝优化。

针对递归中重复子问题的优化最容易想到的就是备忘录memo了，我们只需要拿数组记录下已经被递归过的重复子问题的结果即可。

var rob = function(root) {
  const memo = {};
  dfs(root);
  return dfs(root);

  function dfs(root) {
    if (!root) return 0;

    // 若已被备忘录记录，则剪枝直接返回值
    const rootKey = JSON.stringify(root);
    if (memo[rootKey]) {
      return memo[rootKey];
    }

    // 若决定抢这家，当前子节点就不考虑了，就直接去四个孙子节点再考虑了
    let rob = root.val;
    if (root.left) rob += dfs(root.left.left) + dfs(root.left.right);
    if (root.right) rob += dfs(root.right.left) + dfs(root.right.right);

    // 若决定不抢这家，就在子节点上继续考虑
    const giveup = dfs(root.left) + dfs(root.right);
    const res = Math.max(rob, giveup);

    // 计算出新结果写入备忘录
    memo[rootKey] = res;
    return res;
  }
};

这样运算的效率就提高了许多，时间复杂度能被将至O(N)。

我们也能重新定义dfs子函数，让其返回两个值，分别是抢或者不抢当前节点的最优解。

这样做的好处是，我们可以在每次递归中，都能在后序遍历之后立马算出当前节点取或者不取时的最优解，而不需要再重复进行一次递归，从根本上避免了产生重复子问题，是一种非常巧妙的解法。

var rob = function(root) {
  const [rob, giveup] = helper(root);
  return Math.max(rob, giveup);

  function helper(root) {
    if (!root) return [0, 0];

    // 递归子节点的情况
    const [leftRob, leftGiveup] = helper(root.left);
    const [rightRob, rightGiveup] = helper(root.right);

    // 若决定抢这家，当前的子节点就都必须放弃，结果加上取当前节点的值
    const rob = leftGiveup + rightGiveup + root.val;

    // 若决定不抢这家，当前的子节点的所有情况就都需要被考虑到，其中取最大值
    const giveup = Math.max(leftRob + rightRob, leftGiveup + rightGiveup, leftRob + rightGiveup, leftGiveup + rightRob);

    return [rob, giveup];
  }
};