Leetcode基础刷题之PHP解析(337. House Robber III)


2019-4-29 期一  

这一周开始重新学习树这种结构,介于之前已经做过几道关于二叉树,二叉查找树,平衡二叉查找树的题目,所以找些没做过的题目,最后总结的时候再把之前的题目拿出来复习一下。实践才是硬道理。

关于这道强盗咋么抢更多的钱而不触发报警规则的第三版,之间已经做过版本1,下面是连接:Leetcode基础刷题之PHP解析(198. House Robber)

889a416edaf36307613fbe2ff8778802.png

题目描述

最后的目的还是为了算出最多能抢的金额数。除了根节点,每一个结点只有一个父结点,能直接相连的两个结点不能同时抢,比如说图1这种情况,你要是抢了根节点,那么直接相连的左右子结点你就不能抢。所以你要么抢根节点的左右子结点,要么根节点+根节点->left->right+根节点->right->right.

题目分析

第一种解就是我说的,两种情况之间的比较,递归的调用,如果当前结点的左结点存在,算出不包含左右结点的值,如果右结点存在,算出不包含左右结点的值,然后加上当前结点。第二种就是算出不包含当前结点的左右结点的和,然后取最大的。但是这里存在很大的弊端,看代码。

 /**
     * @param TreeNode $root
     * @return Integer
     */
    function rob($root) {
        if($root==null){
            return 0;
        }
        $res1=$root->val;
        if($root->left !=null) {
            $res1 +=$this->rob($root->left->left)+$this->rob($root->left->right);
        }
        if($root->right !=null){
            $res1 +=$this->rob($root->right->left)+$this->rob($root->right->right);
        }
        
        $res2=$this->rob($root->left)+$this->rob($root->right);
        return max($res1,$res2);
    
    }

重复着进行相同计算,效率低下leetcode直接超时。

14c0ca9ffd35a87cdf7ca0761d1552c1.png

优化代码

如果结点不存在直接返回0,对左右结点分别递归,设置了4个变量,ll和lr分别表示左子结点的左右子结点的最大金额数,rl和rr分别表示右子结点的左右子结点的最大金额数。所以我们最后比较的还是两种情况,第一种就是当前结点+左右子结点的左右子结点的值(即这里定义的ll,lr,rl,rr).第二种是当前结点的左右子结点的值(也就是说我只抢当前结点的子结点,不抢当前结点和孙子结点),再通俗的说就是如果树的层数是3层,要么抢中间一层,要么抢上下两层,谁钱多抢谁(当然我这里指的是三层,并不要误解成隔着一层抢一次,比如看下面其中1种情况,我当然抢的是9+3,而不是9+2)

       9
        1
       2
        3
      
/**
     * @param TreeNode $root
     * @return Integer
     */
    function rob($root) {
       $l=0;$r=0;
        return $this->countMax($root,$l,$r);
    }
    
    function countMax($root,&$l,&$r){
        if($root==null) return 0;
        $ll=0;$lr=0;$rl=0;$rr=0;
        $l=$this->countMax($root->left,$ll,$lr);
        $r=$this->countMax($root->right,$rl,$rr);
        return max($root->val+$ll+$lr+$rl+$rr,$l+$r);
    }

代码马上活过来了。

670575d45c5019ea28273f152dbc1e6c.png

Github整理地址:https://github.com/wuqinqiang/leetcode-php


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D46 893. Groups of Special-Equivalent Strings

>> 下一篇: Leetcode PHP题解--D47 868. Binary Gap