337.打家劫舍 III

打家劫舍 III

小偷发现了一个新的可行窃的地区，这个地区的所有房屋的排列类似于一棵二叉树。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

解析

树形 DP：每个节点返回 [不偷, 偷] 两种状态的最大值。

var rob = function (root) {
  function dfs(node) {
    if (!node) return [0, 0];
    const left = dfs(node.left), right = dfs(node.right);
    const notRob = Math.max(...left) + Math.max(...right);
    const doRob = node.val + left[0] + right[0];
    return [notRob, doRob];
  }
  return Math.max(...dfs(root));
};