[leetcode 96] 不同的二叉搜索树 (python+动态规划/卡塔兰数）

偏执的太偏执、 2023-02-26 12:24 20阅读 0赞

### 目录 ###

*   *  题目描述
     *  解题思路
     *   *   *  方法一：动态规划
             *  方法二：数学法
     *  代码实现
     *   *   *  方法一：动态规划
             *  方法二：数学法
     *  Tips

## 题目描述 ##

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_16_color_FFFFFF_t_70]

> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/unique-binary-search-trees

## 解题思路 ##

#### 方法一：动态规划 ####

给定一个有序序列1···n，为了构建出一棵二叉搜索树，可以遍历每个数字i，将该数字作为树根，将1··· ( i − 1 ) (i - 1) (i−1)作为左子树，将 ( i + 1 ) ⋅ ⋅ ⋅ n (i + 1)···n (i\+1)⋅⋅⋅n序列作为右子树。然后按照相同方式递归构建左子树和右子树。因为构建的每一个二叉树的根节点都不同，所以每棵树都是唯一的。所以原问题可以分解成规模较小的两个子问题，子问题的解可以复用，适合于动态规划问题求解。

定义两个函数：

1.   G ( n ) G(n) G(n)：长度为 n n n的序列能构成的不同二叉搜索树的个数。
2.   F ( i , n ) F(i,n) F(i,n)：以 i i i为根、序列长度为 n n n的不同二叉搜索树个数 ( 1 ≤ i ≤ n ) (1\\le i\\le n ) (1≤i≤n)。

不同的二叉搜索树的总数 G ( n ) G(n) G(n)，是对遍历所有 i ( 1 ≤ i ≤ n ) i(1\\le i\\le n) i(1≤i≤n)的 F ( i , n ) F(i,n) F(i,n)之和。即：  
 G ( n ) = ∑ i = 1 n F ( i , n ) G(n)=\\sum\_\{i=1\}^\{n\} F(i, n) G(n)=i=1∑nF(i,n)  
对于边界情况，当序列长度为1（只有根）或者为0（空树）时结果为1。

给定序列 1 ⋅ ⋅ ⋅ n 1···n 1⋅⋅⋅n，我们选择数字 i i i作为根，则根为 i i i的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，对于笛卡尔积中的每个元素，加上根节点之后形成完整的二叉搜索树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_16_color_FFFFFF_t_70 1]

而且 G ( n ) G(n) G(n)和序列的内容是无关的，之和序列的长度有关。故得到：  
 F ( i , n ) = G ( i − 1 ) ⋅ G ( n − i ) F(i,n)=G(i-1)·G(n-i) F(i,n)=G(i−1)⋅G(n−i)  
比如 F ( 3 , 7 ) = G ( 2 ) ⋅ G ( 4 ) F(3,7)=G(2)·G(4) F(3,7)=G(2)⋅G(4)

所以可以得到递归表达式：  
 G ( n ) = ∑ i = 1 n G ( i − 1 ) ⋅ G ( n − i ) G(n)=\\sum\_\{i=1\}^\{n\} G(i-1) \\cdot G(n-i) G(n)=i=1∑nG(i−1)⋅G(n−i)  
然后从小到大计算G函数即可。

*  复杂度分析：  
    时间复杂度： O ( n 2 ) O(n^2) O(n2)， n n n表示二叉搜索树的结点个数。一共有n个值要求，每次求需要 O ( n ) O(n) O(n)时间复杂度。  
    空间复杂度：  O ( n ) O(n) O(n)。用来存储G数组。

#### 方法二：数学法 ####

方法一种推导出的公式 G ( n ) G(n) G(n)在数学上被称为`卡塔兰数` C n C\_n Cn。其计算公式为：  
 C 0 = 1 , C n + 1 = 2 ( 2 n + 1 ) n + 2 C n C\_\{0\}=1, \\quad C\_\{n+1\}=\\frac\{2(2 n+1)\}\{n+2\} C\_\{n\} C0=1,Cn\+1=n\+22(2n\+1)Cn

*  复杂度分析：  
    时间复杂度： O ( n ) O(n) O(n)，只要循环遍历一次即可。  
    空间复杂度：  O ( 1 ) O(1) O(1)。

## 代码实现 ##

#### 方法一：动态规划 ####

class Solution(object):
        def numTrees(self, n):
            """
            :type n: int
            :rtype: int
            """
            res = [0] * (n+1)
            res[0], res[1] = 1, 1
    
            for i in range(2, n+1):
                for j in range(1, i+1):
                    res[i] += res[j-1] * res[i-j]
            
            return res[n]

#### 方法二：数学法 ####

class Solution(object):
        def numTrees(self, n):
            C = 1
            for i in range(0, n):
                C = 2*(2*i+1)/(i+2) * C
            return int(C)

## Tips ##

1.  不是常见的动态规划状态转移方程，多积累不同的形式；
2.  多积累数学结论。

--------------------

A u t h o r : C h i e r Author: Chier Author:Chier

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_16_color_FFFFFF_t_70]: /images/20230209/9fca47ff7d98455db620fc5385ad95ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDY4MjI5_size_16_color_FFFFFF_t_70 1]: /images/20230209/262abcbd1584443683d8a3589c6e6455.png