337. 打家劫舍 III

打卡!!!每日一题

今天给大家带来一道经典的动态规划题目：打家劫舍系列。

题目描述：337. 打家劫舍 III

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

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

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

示例：

这道题，我们首先要找到一个突破口，如果我们从根节点来出发，那么到底要不要偷根节点，我们无从判断，因为其受制于子节点，所以我们需要找一个不受制于任何一个结点的结点来下手，很明显，叶子节点最适合不过了，因为从叶子开始，其后继结点为空。

同时我们用一个数组来保存每一个结点的盗窃情况[select,notSelect]，即偷和不偷对应的金额。

如果想先遍历叶子节点，在遍历根节点，很明显后序遍历在合适不过了。
对于每个节点来说，都有两种情况：偷和不偷，我们只需要每次取最大值即可。

int[]left=dfs(root.left);
int[]right=dfs(root.right);
1
2

对于我们遍历到的结点，也是如此，也是偷和不偷两种可能

• 偷的话，那么对应的子节点只有不偷一种可能性，所以是l[1],r[1]
• 不偷的话，对于其子节点就没有限制了，可以偷也可以不偷，我们只需要做好判断，每个都确保是最大值即可。

int select = root.val + l[1] + r[1];//偷
int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);//不偷

1
2
3

从上面这个过程我们也很容易看出，为何要采用后序遍历，因为根节点的状态完全依赖于其子节点。

完整代码如下：

public class 打家劫舍III_337 {
    public int rob(TreeNode root) {
        int[] money = dfs(root);
        return Math.max(money[0], money[1]);

    }

    public int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int select = root.val + l[1] + r[1];
        int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{select, noSelect};
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19