4月份很快就过半了，最近都在看WPF，有点落伍了...本来想写一点读书笔记的，还没想好要怎么写。所以为了能够达到每月一篇博客的目标，今天先说一个LeetCode上的面试题：Unique Binary Search Trees。
题目简单翻译过来就是说：
给定n个不同节点，问：可以构造出多少种异构的二叉搜索树。比方说n=3时有5种：
3 3 3 2 1
\ / / / \ \
2 2 1 1 3 2
/ / \ \
1 1 2 3
一般来说，遇到这种问题多半是找规律，总结出数学公式然后解决之。找规律前，首先要看我们有哪些可以利用的条件。
这里可用的条件很有限但也很明确：二叉搜索树。也就是其任意一部分二叉树都满足左子树节点都小于（或者大于）根节点；右子树节点都大于（或者小于）根节点。
我们已经有了n=3的结果，那么来看看n=4时的情况。我们知道，任何一个节点都可以成为一个根节点，那么：
- 如果以1为树根，那么剩下的三个节点都分布在该树的右子树上；
- 如果以2为树根，那么节点1必然是其左子树上的唯一节点，而3、4只可能在其优节点上；
- 如果以3为树根，那么节点2、3在其左子树上，而节点4是其右子树上的唯一节点；
- 如果以4为树根，那么甚于节点都在其左子树上；
这个简单的分析过程很快就将规律呈现了出来！！
对于n=4的情况，其异构结果就是各种独立情况下，左子树和右子树异构方式的排列数之和。用公式表示就是：f(4) = f(0) * f(3) + f(1) * f(2) + f(2) * f(1) + f(3) * f(0)。整一个典型的递归实现。唯一需要考虑的点就是你需要缓存一下中间数据，因为f(2)和f(3)分别被调用了2次。
class Solution {
public:
int numTrees(int n) {
static vector<int> cached(, );
if (n > cached.size())
{
cached.resize(n, );
}
if ( == n)
{
return ;
}
if (cached[n - ] != )
{
return cached[n - ];
}
else
{
for (int i = ; i < n; ++i)
{
cached[n - ] += numTrees(i) * numTrees(n - i - );
}
return cached[n - ];
}
}
};
顺带因为打算以后要有Python，所以附带上Python的代码。刚开始学着写Python，写着有点难过...（有没有更好的写法？）
class Solution:
# @return an integer
def numTrees(self, n):
if 0 == n:
return 1 cached = [1]
if n > len(cached):
result = 0;
for i in range(n):
index = n - i - 1 left_part_result = self.numTrees(i)
right_part_result = self.numTrees(index) result += left_part_result * right_part_result if index == len(cached):
cached[len(cached):] = [right_part_result] cached[len(cached):] = [result] return result
else:
return cached[n - 1];
这题目的背景是一个称之为Catalan Number的数。也可以参看百度百科。通过了解Catalan Number，我们会发现他的诸多应用。比方说凸多边形的最优三角划分就是这个问题的拓展。