LeetCode-HouseRobberIII

发表于

题目链接

这是一道dp题目，需要拆解子问题，分析如下:
dp photo

a点可抢劫的最大值，包括两种情况，包含a点、不包含a点。
包含a点，其左右节点就不能包含；
不包含a点，则为其左右节点可抢劫最大值之和。

1
2
3
best_with(a) = a.val + best_without(b) + best_without(c)

best_without(a) = max(best_with(b),best_without(b)) + max(best_with(c),best_without(c))

按照上面的解法，写出代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int rob(TreeNode root) {
        if (root == null ) return 0;
        int selectCur = root.val;
        if (root.left != null) selectCur += (rob(root.left.left)+rob(root.left.right));
        if (root.right != null) selectCur += (rob(root.right.left)+rob(root.right.right));
        int unselectCur = rob(root.left)+rob(root.right);
        return Math.max(selectCur,unselectCur);
    }
}

可是提交时，会有TLE。我们在计算子节点可抢劫的最大值时进行了重复计算。从下面的代码里，可以看出有重复计算。

1
2
rob(root.left.left)
rob(root.left)

使用的方法：在计算节点可抢劫的最大值时，存储包含当前节点的最大值best_with和不包含当前节点的最大值best_without,返回一个数组。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int rob(TreeNode root)
    {
    	 int[] rst = {0,0};
    	 rst = dfs(root);
        return Math.max(rst[0],rst[1]);
    }
    public int[] dfs(TreeNode root) {
        int [] robber = {0,0};
        if (root != null)
        {
            int[] robLeft = dfs(root.left);  
            int[] robRight = dfs(root.right);
            robber[0] = Math.max(robLeft[0],robLeft[1])+Math.max(robRight[0],robRight[1]);
            robber[1] = root.val+robLeft[0]+robRight[0];
        }
        return robber;
    }
}

robber[1]存储的是在包含当前节点的情况下，当前节点可抢劫的最大值。
robber[0]存储的是在不包含当前节点情况下，当前节点可抢劫的最大值。

参考：
http://blog.csdn.net/happyaaaaaaaaaaa/article/details/50880121
https://docs.google.com/document/d/1NPojCYmFOSg-GvYfOKKS6dkp6VBNbjVmYho5nl8YI3M/edit#heading=h.8xfeu8ymemfz