337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例 1:

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

• 树的节点数在 [1, 10^4] 范围内
• 0 <= Node.val <= 10^4

动态规划+递归+前序遍历+备忘录（哈希表）

class Solution {
    Map<TreeNode, Integer> memo = new HashMap<>();

    // 主函数，计算从根节点开始的最大偷窃金额
    public int rob(TreeNode root) {
        if (root == null) return 0;
        // 利用备忘录消除重叠子问题
        if (memo.containsKey(root)) return memo.get(root);
        
        // 抢，然后去下下家
        int do_it = root.val
                + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right))
                + (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
        // 不抢，然后去下家
        int not_do = rob(root.left) + rob(root.right);

        int res = Math.max(do_it, not_do);
        memo.put(root, res);
        return res;
    }
}

时间复杂度O(N)，因为备忘录的大小就是n，所以需要遍历所有节点来计算出每个节点的值，计算完一边就可以了，以后就是直接取，O(1)。如果没有备忘录，则时间复杂度应该也是O(n)。

空间复杂度O(N)，栈空间和备忘录

动态规划-递归+后序遍历，不需要备忘录。

为什么后序不需要备忘录而前序遍历需要？因为父节点只有一个，而子节点有多个，有多个子节点就意味着有多种方式到达同一个节点，所以需要去重

class Solution {
    int rob(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }

    int[] dp(TreeNode root) {
        if (root == null) return new int[] { 0, 0 };

        int[] left = dp(root.left);
        int[] right = dp(root.right);
        
        // 抢 root，下家就不能抢了
        int rob = root.val + left[0] + right[0];
        // 不抢，下家可抢可不抢，取决于收益大小。重点。
        int not_rob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);

        return new int[] { not_rob, rob };
    }
}

• 时间复杂度：$O(n)$。假设二叉树的节点个数为 $n$。我们可以看出，以上的算法对二叉树做了一次后序遍历，时间复杂度是 $O(n)$。
• 空间复杂度：$O(n)$。虽然优化过的版本省去了哈希表的空间，但是栈空间的使用代价依旧是 $O(n)$，故空间复杂度不变。