LeetCode.337 打家劫舍
coconutnut
 2020-03-12 23:05:50      
题目地址

暴力抢劫

写出来倒是挺快，结果发现时间爆炸

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

    public int find(TreeNode root, boolean isGap){
        if(root==null){
            return 0;
        }
        int ret = 0;
        if(!isGap){
            // 本层抢，下层不能抢
            ret+=root.val;
            ret+=find(root.left,false);
            ret+=find(root.right,false);
        }else{
            int next1 = Math.max(find(root.left,true),find(root.left,false));
            int next2 = Math.max(find(root.right,true),find(root.right,false));
            ret = next1 + next2;
        }
        
        return ret;
    }
}
1
2
执行用时：2817 ms
内存消耗：39.3 MB

这样写每次都递归找了至少2次、甚至4次子节点

相当于把二叉树省下来的log又给翻倍乘回去了

机智的劫匪

看了题解中一次返回2种情况，修改一下

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
class Solution {
    public int rob(TreeNode root) {
        int[] ans = find(root);
        return Math.max(ans[0],ans[1]);
    }

    public int[] find(TreeNode root){
        // ret0-本层不抢；ret1-本层抢
        int[] ret = new int[2];

        if(root==null){
            return ret;
        }
        
        int[] left = find(root.left);
        int[] right = find(root.right);
        
        // 下层爱抢不抢
        ret[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        // 下层不能抢
        ret[1] = root.val + left[0] + right[0];
        
        return ret;
    }
}
1
2
执行用时：1 ms
内存消耗：41.6 MB

这样就只遍历了1次

总结

递归中如果要分情况讨论，一次返回多个结果，不要多次调用递归