本文主要是介绍LeetCode96. Unique Binary Search Trees，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 一、题目
- 二、题解
一、题目
Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3
Output: 5
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 19
二、题解
法一：动态规划法
class Solution {
public:int numTrees(int n) {vector<int> dp(n+1,0);dp[0] = 1;for(int i = 1;i <= n;i++){for(int j = 1;j <= i;j++){dp[i] += dp[j-1] * dp[i-j];}}return dp[n];}
};
法二：利用卡特兰数
注意当n = 19时，int会溢出
class Solution {
public:int numTrees(int n) {long long res = 1;for(int i = 0;i < n;i++){res = res * 2 * (2 * i + 1) / (i + 2);}return (int)res;}
};
这篇关于LeetCode96. Unique Binary Search Trees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
