Leetcode刷题之PHP解析(96. Unique Binary Search Trees)


 2019-7-22 星期一 开始吧

Leetcode刷题之PHP解析( 154. Find Minimum in Rotated Sorted Array II)


1ee8b83cc871b1f823bd412d4286209f.png

给定一个整数n,求从1到n有多少组二叉查找树组合。

好吧,这道题其实是一个卡塔兰数例子。。。只听过斐波拉契数。。特意从维基百科截了一张图你们感受一下。

4b9865caab6876aa621867dd2899ea79.png


求最终有多少种情况,其实本质上就是左子树的情况加右子树的情况。如果n等于0,值等于1。因为空树也是二叉查找树。n等于1,1就是根节点,左右子树都为空,所以结果也是1.

如果n等于2的话,1,2都能作为树的根节点,如果1为根节点,那么左子树就是空,右子树就是2

dp[2]=dp[0]*dp[1]+dp[1]*dp[0]=2

如果n=3,1,为根节点的话,左子树没节点。右子树两个结点,2为根结点的话,左右子树各一个结点,3为根节点的话和1是根节点相反的情况

dp[3]=dp[0]*dp[2]+dp[1]*dp[1]+dp[2]*dp[0]

代码实现

    /**
     * @param Integer $n
     * @return Integer
     */
    function numTrees($n) {
        $dp[0]=$dp[1]=1;
        for($i=2;$i<=$n;$i++){
            for($j=0;$j<$i;$j++){
                $dp[$i]+=$dp[$j]*$dp[$i-$j-1];
            }
        }
        return $dp[$n];
    }

Vote Vote Cancel Collect Collect Cancel

<< 上一篇: 基于 Nginx + ModSecurity 构建防火墙

>> 下一篇: Leetcode PHP题解--D108 404. Sum of Left Leaves