leetcode 337号问题

Question

public int rob1(TreeNode root){
        count++;
        if(root==null){
            return 0;
        }//如果根节点为空的话，返回0就可以了
        int oneSolution=rob1(root.left)+rob1(root.right);//第一种情况，是不偷取根节点，而选择偷取它的左右子节点的和
        //第二种情况，偷取根节点，那就只能继续偷取根节点的左节点的左右节点和右节点的左右节点
        int twoSolution=root.val;
        if(root.left!=null)
            twoSolution+=rob1(root.left.left)+rob1(root.left.right);
        if(root.right!=null)
            twoSolution+=rob1(root.right.left)+rob1(root.right.right);
        //比较这两个情况的收益的大小,将较大的赋值给res
        int res=Math.max(oneSolution,twoSolution);
        return res;
    }
public static void main(String[]args){
        TreeNode node1=new TreeNode(3);
        TreeNode node2=new TreeNode(4);
        TreeNode node3=new TreeNode(5);
        TreeNode node4=new TreeNode(1);
        TreeNode node5=new TreeNode(3);
        TreeNode node6=new TreeNode(1);
//        TreeNode node7=new TreeNode(8);
        node2.left=node4;node2.right=node5;node3.right=node6;node1.left=node2;node1.right=node3;
        System.out.println(new NinetyThree().rob1(node1));
        System.out.print(count);
    }

老师，我的这个递归的方法，我觉的它的时间复杂度为O(2^n)，因为对于每一个节点，都有两种情况，一共有n个节点，所以我觉得应该会有2的n次方种情况，但是我放了几种树到测试用例上，并没有跟我想的一样，搞不懂为什么

Answer 1

提问者 pfco 2019-05-18 18:42:50

是不是因为我的测试的规模太小了

• liuyubobobo #1

  是的，这是一个指数级算法。但是n太小测不出来。在Leetcode上提交这个代码，也能得到AC，他因为Leetcode的测试用例也比较小。但很明显，用时会远远超过使用记忆化搜索的思路：）继续加油！：）

Answer 2

提问者 pfco 2019-05-18 17:22:55

老师，那个重叠子问题我之前的发错了，我已经想通了那个重叠的子问题