Leetcode_96_Unique Binary Search Trees

本文是在学习中的总结,欢迎转载但请注明出处:http://blog.csdn.net/pistolove/article/details/43198929

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个节点,求能组成多少个二叉树。

(2)该题和给定n个数字,求其所有进栈出栈顺序总个数是相同的,详情参看数据结构。

(3)本题是运用递归进行实现。

递推关系为: f(n)=C(2n,n)/(n+1) (n=1,2,3,...)。

递归式为: f(n)=f(n-1)*(4*n-2)/(n+1)。

通过该公式进行递归即可得到答案。但是通过递归实现的算法效率显然要低一些。

递推过程:

当n=1时,只有1个根节点,则能组成1种,令n个节点可组成的二叉树数量表示为f(n),  则f(1)=1;

当n=2时,1个根节点固定,还有n-1个节点,可以作为左子树,也可以作为右子树, 即:f(2)=f(0)*f(1)+f(1)*f(0)=2,则能组成2种。

当n=3时,1个根节点固定,还有n-1=2个节点,可以在左子树或右子树, 即:f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=5,则能组成5种。

当n>=2时,有f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0)

(4)希望本文对你有所帮助。

算法代码实现如下:

	/**
	 * @author liqq
	 */
    public int numTrees(int n) {
        int i;
    	int result = 0;
    	if(n==0) return 1;
    	if(n==1) return 1;

    	for (i = n-1; i>=0 ; i--) {
			result = result + numTrees(i)*numTrees(n-i-1);
		}
    	return result;
    }
上一篇:tween.js是一款可生成平滑动画效果的js动画库。tween.js允许你以平滑的方式修改元素的属性值。它可以通过设置生成各种类似CSS3的动画效果。


下一篇:ios开发——实用技术OC篇&地图与定位