337. House Robber III

DFS + Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> notRobMoneyCache = new IdentityHashMap<>();
        Map<TreeNode, Integer> robMoneyCache = new IdentityHashMap<>();

        return rob(root, false, notRobMoneyCache, robMoneyCache);
    }

    private int rob(TreeNode node, boolean parentRobbed, Map<TreeNode, Integer> notRobMoneyCache, Map<TreeNode, Integer> robMoneyCache) {
        if (node == null) {
            return 0;
        }

        // not rob node
        Integer cachedNotRobMoney = notRobMoneyCache.get(node);
        int notRobMoney;
        if (cachedNotRobMoney != null) {
            notRobMoney = cachedNotRobMoney;
        } else {
            notRobMoney = rob(node.left, false, notRobMoneyCache, robMoneyCache) + rob(node.right, false, notRobMoneyCache, robMoneyCache);
            notRobMoneyCache.put(node, notRobMoney);
        }

        // rob node
        int robMoney = 0;
        if (!parentRobbed) {
            Integer cachedRobMoney = robMoneyCache.get(node);
            if (cachedRobMoney != null) {
                robMoney = cachedRobMoney;
            } else {
                robMoney += node.val;
                if (node.left != null) {
                    robMoney += rob(node.left, true, notRobMoneyCache, robMoneyCache);
                }
                if (node.right != null) {
                    robMoney += rob(node.right, true, notRobMoneyCache, robMoneyCache);
                }
                robMoneyCache.put(node, robMoney);
            }
        }

        return Math.max(notRobMoney, robMoney);
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[2];
        }

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

        // 注意此处，不偷窃当前节点时，子节点可以被偷窃，也可以不被偷窃，也可以其中一个子节点被偷窃，另一个不被偷窃
        int notRob = left[1] + right[1];
        notRob = Math.max(notRob, left[0] + right[0]);
        notRob = Math.max(notRob, left[0] + right[1]);
        notRob = Math.max(notRob, left[1] + right[0]);
        int rob = root.val + left[0] + right[0];
        return new int[]{notRob, rob};
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[2];
        }

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

        // 注意此处，不偷窃当前节点时，此树能偷窃到的最大金额等于左子树能够偷窃到的最大金额加上右子树能偷窃到的最大金额
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        int rob = root.val + left[0] + right[0];
        return new int[]{notRob, rob};
    }
}

References

337. House Robber III