Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Input: 3
Output: 5
Explanation:
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
题意:
给定n个节点,可形成多少种不同的BST
思路:
如果数组为空,毫无疑问,只有一种BST,即空树, f(0) =1。
如果数组仅有一个元素{1},只有一种BST,单个节点, f(1) =1。
如果数组有两个元素{1,2}, 那么有如下2种可能, f(2)=2。
如果数组有三个元素{1,2,3}, 那么有如下5种可能, f(3)=5。
1 1 2 3 3
\ \ / \ / /
3 2 1 3 2 1
/ \ / \
2 3 1 2
由此得出规律,
对于任意以i为根节点的二叉树,
其左子树的值一定小于i,也就是[0, i - 1]区间,
而右子树的值一定大于i,也就是[i + 1, n]区间。
假设左子树有m种排列方式,而右子树有n种,则对于i为根节点的二叉树总的排列方式就是m x n
卡特兰数(Catalan)递归式:f(n) = f(1)*f(n-1) + f(2)*f(n-2) + ... + f(n-1)f(1)