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

2019-4-29 星期一  开始吧

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

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

题目描述

最后的目的还是为了算出最多能抢的金额数。除了根节点，每一个结点只有一个父结点，能直接相连的两个结点不能同时抢，比如说图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直接超时。

优化代码

如果结点不存在直接返回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);
    }

代码马上活过来了。

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