337. 打家劫舍 III

337. 打家劫舍 III

1.想法:

从根节点选起,分为两种情况
1.选择了根,那么左右子节点都不能选择,但是其子节点的节点不受影响.

image.png

2.不选择根,其值为选择左边的加上选择右边的.

image.png
因为中间一定存在根节点,使得左右之间有界限,那么左右子节点到底选不选,例如2,到底要不要2,这个这个问题就变成了原问题,但是规模减少一
image.png

总结:这个过程是一个递归的过程,那么我们用一个标记位来表示这个节点能不能选.可以递归为:

2.代码

1.没有任何的辅助空间

  public int rob(TreeNode root) {
      //第一个参数是节点,第二个是是否可选
       return myRob(root,true);
    }

    private int myRob(TreeNode root, boolean b) {
       //如果为null直接返回0
        if(root == null)return 0;
        //如果可选,那么就选择是否选择root节点
        if(b){
           //从是否选择root节点和不选择root节点中挑出最大的
            return Math.max(myRob(root.left,false)+myRob(root.right,false)+root.val,
                    myRob(root.left,true)+myRob(root.right,true));
        }
        不可选择的时候直接选择左右子节点
        return myRob(root.left,true)+myRob(root.right,true);
    }

image.png

可以看到时间还是很高的,我们认真分析一下,肯定是递归过程中重复计算的太多了

2.优化一,优化重复计算

我们可以明显看到当root节点可选的时候和root节点不可选的时候都做了不选root节点的选项

image.png

我们把公共部分提出来.

public int rob(TreeNode root) {
       return myRob(root,true);
    }

    private int myRob(TreeNode root, boolean b) {
       if(root == null)return 0;
      //root可选与不可选的公共部分
        int noChoice = myRob(root.left,true)+myRob(root.right,true);
        if(b){
            return Math.max(myRob(root.left,false)+myRob(root.right,false)+root.val,
                    noChoice);
        }
        return noChoice;
    }

image.png

总结:有部分优化,但是还是不理想,归根到底,我们在做的时候,对root可选与不可选只是提出一部分,但是当root可选与不可选到了子节点的子节点时,就继续重复了.

image.png

3.优化二,优化存储,避免重复计算

利用Map来存储节点是否被计算,这样会节省计算的时间

 Map<TreeNode,Integer> temp = new HashMap<>();
    public int rob(TreeNode root) {
       return myRob(root,true);
    }

    private int myRob(TreeNode root, boolean b) {
        if(root == null)return 0;
         //不选择当前节点
        int noChoice=0,noChoiceLeft=0,noChoiceRight=0,choice=0;
        //如果包含了该节点,直接返回,不包含的话计算后更新
        if(temp.containsKey(root.left)){
            noChoiceLeft = temp.get(root.left);
        }else{
            noChoiceLeft = myRob(root.left,true);
            temp.put(root.left,noChoiceLeft);
        }
        if(temp.containsKey(root.right)){
            noChoiceRight = temp.get(root.right);
        }else{
            noChoiceRight = myRob(root.right,true);
            temp.put(root.right,noChoiceRight);
        }
        noChoice = noChoiceLeft + noChoiceRight;
        //如果可以选择当前节点
        if(b){
            int choiceLeft = myRob(root.left,false);
            int choiceRight = myRob(root.right,false);
            //选择后的结果
            choice = choiceLeft+choiceRight+root.val;
            //比较不选择和选的大小
            return Math.max(choice,noChoice);
        }
        return noChoice;
    }

image.png