LeetCode-Unique Binary Search Trees

研究生开学以来一直在看书看文献，很少有机会去写代码。为了不让以后校招时被虐的太惨，准备每天看一道LeetCode上的题，练练手。因此准备开一个新的专题，记录下LeetCode上的一些有意思的小的算法题。不要问我什么是LeetCode，自行google噢。题目传送门在此

题目

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. enter image description here

分析

又是一道关于BSTree的题目，不过没有涉及到其他高深的特性。我们只需要了解什么是BST就行。 BST中文名是二叉搜索树，节点左子树的值都要小，右子树的值都要大。觉得我说的比较绕口，移步至BST Wiki 对于这道题，我们可以用递归，或者说成动态规划，的思路去解决。譬如说对于参数值n，我们可以考虑左边1个节点，右边n-2个节点；左边2个节点，右边n-3个节点等等。对于每个子树，在进行这样的划分，这样就能看到动态规划的影子了。我们需要一个List来保存结果，下标是其总节点数，数值是其组成BST的个数。show 代码就好理解了。

def numTrees(n):
results = [1, 1] + [0 for i in range(n)]  #0和1 都只有一种情况
for i in range(2, n+1):
    for j in range(i):
        results[i] += results[j] * results[i-j-1]
return results[n]

# test
if __name__ == "__main__":
    print numTrees(4)

--EOF--