一、题目
1、算法题目
“给定一个整数n，求由n个节点组成的节点值从1到n的互不相同的搜索二叉树。”
题目链接：
来源：力扣（LeetCode）
链接：96. 不同的二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
网络异常，图片无法展示
|
示例 1： 输入： n = 3 输出： 5 复制代码
示例 2： 输入： n = 1 输出： 1 复制代码
二、解题
1、思路分析
这道题95题【不同的二叉搜索树 Ⅱ】很相似，不同的点在于这道题要找出互不相同的二叉搜索树。
上一题我们使用了递归的方法，找出所有能构建的二叉搜索树，然后再在其中找出合法的二叉搜索树。
而在遍历每个数字的过程中，可以将该数字作为树根，然后将1...i-1作为左子树，i+1...n作为右子树，然后按照同样的方式递归构建左子树和右子树。
也就是把一个问题分成两个小问题，因此可以使用动态规划来解这道题：
- 假设n个节点存在二叉排序树的个数为Gn，然后每个数字作为根也就是f(1)-f(n)，则
- G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)
- 当i为根节点时，其左子树节点数为1...i-1，右子树的节点数为i+1...n，则
- f(i)=G(i-1) * G(n-i)
- 综合两个公式可以得到卡特兰数公式：
- G(n) = G(0) * G(n-1) + G(1) * (n-2) + ... + G(n-1) * G(0)
2、代码实现
代码参考：
class Solution { public int numTrees(int n) { // 提示：我们在这里需要用 long 类型防止计算过程中的溢出 long C = 1; for (int i = 0; i < n; ++i) { C = C * 2 * (2 * i + 1) / (i + 2); } return (int) C; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n表示二叉搜索树的节点个数。
空间复杂度： O(1)
只需要常量级的空间存放变量。
三、总结
这里分享一个面向测试用例的编程代码，非常的秀：
class Solution { public: int numTrees(int n) { switch(n){ case 1: return 1; case 2: return 2; case 3: return 5; case 4: return 14; case 5: return 42; case 6: return 132; case 7: return 429; case 8: return 1430; case 9: return 4862; case 10: return 16796; case 11: return 58786; case 12: return 208012; case 13: return 742900; case 14: return 2674440; case 15: return 9694845; case 16: return 35357670; case 17: return 129644790; case 18: return 477638700; case 19: return 1767263190; default: return 0; } } }; 复制代码
因为答案的值是固定的，所以这么写。。。好像也能通过。。。
