首页 > 代码库 > leetcode[94] Unique Binary Search Trees
leetcode[94] Unique Binary Search Trees
给定n，那么从1,2,3...n总共可以构成多少种二叉查找数呢。例如给定3
Given n = 3, there are a total of 5 unique BST‘s.
1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3
思路：
我们考虑头结点i，那么所有比i小的都在i的左边，比i大的都在i的右边。也就是以i为开头的是i的左边的可能*i右边的可能，然后遍历i从1到n，所有可能相加就是我们的结果。
由公式 h[n] = h[0]*h[n-1] + h[1]*h[n-1] + ... + h[n-1]*h[0]; 可得如下：
class Solution {public: int numTrees(int n) { if (n == 1) return 1; vector<int> ans(n+1); ans[0] = 1; ans[1] = 1; for (int i = 2; i <= n; i++) for (int j = 0; j < i; j++) { ans[i] += ans[j]*ans[i-j-1]; } return ans[n]; }};
其实这是一个卡特兰数，直接用公式C2n选n除以n+1则如下：
class Solution {public: int numTrees(int n) { if (n == 1) return 1; long long denominator = 1, numerator = 1; int cnt = 2 * n; while(cnt > n) denominator *= cnt--; while(cnt > 0) numerator *= cnt--; return denominator/numerator/(n+1); }};
还可以用递归：
class Solution {public: int numTrees(int n) { return numTrees(1,n); } int numTrees(int start, int end) { if (start >= end) return 1; int totalNum = 0; for (int i=start; i<=end; ++i) totalNum += numTrees(start,i-1)*numTrees(i+1,end); return totalNum; }};
leetcode[94] Unique Binary Search Trees
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。