LeetCode96：不同的二叉搜索树

本文主要是介绍LeetCode96：不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

代码

/*dp[i]：表示i个节点有dp[i]个不同的二搜索叉树递推公式：dp[i] += dp[j-1] * dp[i-j], j代表头节点 dp[j-1]代表左子树的形态个数dp[i-j]代表右子树的形态个数初始化：dp[0] =1 , dp[1] = 1, dp[2] = 2;遍历顺序：从小到大*/
class Solution {
public:int numTrees(int n) {if (n == 0) return 1;else if (n <= 2) return n;vector<int> dp(n + 1);dp[0] = 1, dp[1] = 1, dp[2] = 2;for (int i = 3; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}}int  result = 0;for (int num : dp)result += num;return result;}
};

这篇关于LeetCode96：不同的二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---