[leetcode题解]96. Unique Binary Search Trees

如果把示例数据的顺序改一下,就可以看出规律了。

1     1       2       3   3
 \     \     / \     /   /
  3     2   1   3   2   1
 / 		 \         /     \
2         3       1       2

比如,以 1 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 0 个元素的树,
右子树是 2 个元素的树。以 2 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 1
个元素的树,右子树也是 1 个元素的树。依此类推。
当数组为 1,2,3,…,n 时,基于以下原则的构建的 BST 树具有唯一性:以 i 为根节点的树,其左
子树由 [1, i-1] 构成,其右子树由 [i+1, n] 构成。
定义 f(i) 为以 [1,i] 能产生的 Unique Binary Search Tree 的数目,则
如果数组为空,毫无疑问,只有一种 BST,即空树,f(0) = 1。
如果数组仅有一个元素 1,只有一种 BST,单个节点,f(1) = 1。
如果数组有两个元素 1,2,那么有如下两种可能

1      2
 \    /
  2  1

f(2) = f(0) + f(1) ,1 为根的情况f(1) = f(0) ,2 为根的情况
再看一看 3 个元素的数组,可以发现 BST 的取值方式如下:
f(3) = f(0) + f(2) ,1 为根的情况
f(3) += f(1) + f(1) ,2 为根的情况
f(3) += f(2) + f(0) ,3 为根的情况
所以,由此观察,可以得出 f 的递推公式为

f(i) =f(k − 1) × f(i − k) k=1…i
至此,问题就可以用一个递推关系很好的解决了。

leetcode题目如下:
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

代码如下:

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
	int numTrees(int n) {
		int *res = new int[n + 1];
		res[0] = res[1] = 1;
		for (int i = 2; i <= n; ++i)
		{
			res[i] = 0;
			for (int j = 0; j < i; ++j)
			{
				res[i] += res[j] * res[i - 1 - j];
			}
		}
		int t = res[n];
		delete[] res;
		return t;
	}
};

int main()
{
	Solution so;
	int n = so.numTrees(3);

	cout << n << endl;

	return 0;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]96. Unique Binary Search Trees

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/48.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注