【LeetCode刷题笔记（四十四）】之 96. 不同的二叉搜索树

女爷i 2023-10-07 15:08 30阅读 0赞

### 本文章由公号【开发小鸽】发布！欢迎关注！！！ ###

**老规矩–妹妹镇楼：**

![20200721223424816.JPG][]

### 一． 题目 ###

#### （一） 题干 ####

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

#### （二） 示例 ####

输入: 3
    输出: 5
    解释:
    给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

### 二． 题解 ###

#### （一） 思路 ####

二叉搜索树，树的根节点大于左子树中的所有值，小于右子树的所有值。关于树的题目，一般都要往递归和动态规划方面去思考。很明显，这个题目可以使用动态规划解决，n个数的二叉搜索树数量是依赖于n-1个数的二叉搜索树的数量的，因此可以从n=1开始迭代，迭代n次。

每次迭代中，选取列表中的一个数作为根节点，分出左右子树。每个子树能够构成的二叉搜索树只和每个子树的节点个数相关，与节点的内容是没有关系的，因为每个子树都是有序的，二叉搜索树都是按照顺序排列的。因此，每个根节点能组成的二叉搜索树的种类为左子树的种类乘以右子树的种类。而左右子树的种类数在n值较小的迭代中已经求出了，因此，直接使用即可。

#### （二） 代码实现 ####

Java：

class Solution {
        
        public int numTrees(int n) {
        
            int[] dp = new int[n+1];
            dp[0] = 1;
            dp[1] = 1;
            for(int i = 2; i <= n; ++i){
        
                for(int j = 1; j <= i; ++j){
        
                    dp[i] += dp[j-1] * dp[i-j];
                }
            }
            return dp[n];
        }
    }

[20200721223424816.JPG]: https://img-blog.csdnimg.cn/20200721223424816.JPG