首页 > 代码库 > LeetCode Unique Binary Search Trees
LeetCode Unique Binary Search Trees
Given n, how many structurally unique BST‘s (binary search trees) that store values 1...n?
For example,
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
解题思路：求一个序列1,2,3.。n对应的值，想到递推，DP，该题也就是如何构造一个二叉查找树，
如果1为顶点，则左边没有节点，右子树有n-1个节点，且这n-1个节点也是二叉查找树
如果2为顶点，则左边有1个节点，右边有n-2个节点，且左右都为二叉查找树
。。。
得出递推公式d[n] = ∑d[j]*d[n-j-1];且d[0]=d[1]=1
于是可解。
class Solution {public: int numTrees(int n) { int result[n+1]; for(int i=0;i<=n;++i)result[i] = 0; result[0] = 1; result[1] = 1; for(int i=2;i<=n;++i) { for(int j=1;j<=i;++j) { result[i] += result[j-1]*result[i-j]; } } return result[n]; }};
LeetCode Unique Binary Search Trees
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。