題目
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組成的二叉搜索樹敢课。
先給出網(wǎng)上的定義：
BST(Binary Search Tree),二叉查找樹;
性質(zhì)：
若結(jié)點(diǎn)的左子樹不空潦闲，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;
若結(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;
該結(jié)點(diǎn)的左翁锡、右子樹也分別為二叉查找樹;
遍歷：
對于一個(gè)已知的二叉查找樹,從小到大輸出其節(jié)點(diǎn)的值;
只需對其進(jìn)行二叉樹的中序遍歷即可;
即遞歸地先輸出其左子樹,再輸出其本身,然后輸出其右子樹;
遍歷的時(shí)間復(fù)雜度為O(n);
查找：
對于一個(gè)已知的二叉查找樹x;
在其中查找特定的值k,函數(shù)Search返回指向值為k的節(jié)點(diǎn)指針;
若找不到則返回0,算法時(shí)間復(fù)雜度為O(h),h為樹的高度;
理想情況下時(shí)間復(fù)雜度為lgn;
最大值和最小值：
要查找二叉查找樹中具有最小值的元素;
只要從根節(jié)點(diǎn)開始,沿著左子樹找到最左邊的節(jié)點(diǎn)就可以了;
反之沿著右子樹查找則可以求最大值;
插入：
從根節(jié)點(diǎn)開始插入;
如果要插入的值小于等于當(dāng)前節(jié)點(diǎn)的值肆氓，在當(dāng)前節(jié)點(diǎn)的左子樹中插入;
如果要插入的值大于當(dāng)前節(jié)點(diǎn)的值尤蛮，在當(dāng)前節(jié)點(diǎn)的右子樹中插入;
如果當(dāng)前節(jié)點(diǎn)為空節(jié)點(diǎn)抡爹，在此建立新的節(jié)點(diǎn)腌逢，該節(jié)點(diǎn)的值為要插入的值，左右子樹為空逐沙，插入成功;
刪除：
如果該沒有子女哲思，直接刪除;
如果該結(jié)點(diǎn)只有一個(gè)子女，則刪除它吩案，將其子女的父親改為它的父親;
如果該結(jié)點(diǎn)有兩個(gè)子女棚赔，先用其后繼替換該節(jié)點(diǎn)，其后繼的數(shù)據(jù)一并加在其后;
可以思考一定數(shù)目的二叉搜索樹數(shù)目是固定的徘郭，因此任選一個(gè)數(shù)當(dāng)根節(jié)點(diǎn)靠益，那么小于該數(shù)的數(shù)都會(huì)在其左子樹，而大于該數(shù)的都會(huì)在其右子樹残揉。該種情況的數(shù)目就為左子樹的數(shù)目和右子樹數(shù)目的乘積胧后。
即為動(dòng)態(tài)規(guī)劃的思想。
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];
}
