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

 2019-7-22 星期一 开始吧

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

题目描述

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

题目分析

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

求最终有多少种情况，其实本质上就是左子树的情况加右子树的情况。如果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];
    }