题目
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-n组成的二叉搜索树。
先给出网上的定义：
BST(Binary Search Tree),二叉查找树;
性质：
若结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值;
若结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值;
该结点的左、右子树也分别为二叉查找树;
遍历：
对于一个已知的二叉查找树,从小到大输出其节点的值;
只需对其进行二叉树的中序遍历即可;
即递归地先输出其左子树,再输出其本身,然后输出其右子树;
遍历的时间复杂度为O(n);
查找：
对于一个已知的二叉查找树x;
在其中查找特定的值k,函数Search返回指向值为k的节点指针;
若找不到则返回0,算法时间复杂度为O(h),h为树的高度;
理想情况下时间复杂度为lgn;
最大值和最小值：
要查找二叉查找树中具有最小值的元素;
只要从根节点开始,沿着左子树找到最左边的节点就可以了;
反之沿着右子树查找则可以求最大值;
插入：
从根节点开始插入;
如果要插入的值小于等于当前节点的值，在当前节点的左子树中插入;
如果要插入的值大于当前节点的值，在当前节点的右子树中插入;
如果当前节点为空节点，在此建立新的节点，该节点的值为要插入的值，左右子树为空，插入成功;
删除：
如果该没有子女，直接删除;
如果该结点只有一个子女，则删除它，将其子女的父亲改为它的父亲;
如果该结点有两个子女，先用其后继替换该节点，其后继的数据一并加在其后;
可以思考一定数目的二叉搜索树数目是固定的，因此任选一个数当根节点，那么小于该数的数都会在其左子树，而大于该数的都会在其右子树。该种情况的数目就为左子树的数目和右子树数目的乘积。
即为动态规划的思想。
int a[100000];
int numTrees(int n) {
a[0]=1;
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++)
{
int ans=0;
for(int j=1;j<=i;j++)
{
ans+=a[j-1]*a[i-j];
}
a[i]=ans;
}
return a[n];
}
