Unique Binary Search Trees：求生成二叉排序树的个数。
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
算法分析：类似上阶梯，简单的动态规划问题。当根节点为i时，比i小的节点有i-1个，比i大的节点有n-i个，所以，i为根节点能够生成二叉排序树的个数是
nums[n] += nums[i-1]*nums[n-i]，i从1到n。
public class UniqueBinarySearchTrees
{
public int numTrees(int n)
{
if(n <= 0)
{
return 0;
}
int[] res = new int[n+1];
res[0] = 1;
res[1] = 1;
for(int i = 2; i <= n; i ++)
{
for(int j = 1; j <= i; j ++)//j为根节点
{
res[i] += res[j-1]*res[i-j];
}
}
return res[n];
}
}
Unique Binary Search Trees2：求生成二叉排序树的根节点的集合
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
算法分析：这个不是求个数，而是求生成树根节点。使用递归。
public class UniqueBinarySearchTreesII
{
public List<TreeNode> generateTrees(int n)
{
if(n <= 0)
{
return new ArrayList<TreeNode>();
} return helper(1, n);
} public List<TreeNode> helper(int m, int n)
{
List<TreeNode> res = new ArrayList<>();
if(m > n)
{
res.add(null);
return res;
} for(int i = m; i <= n; i ++)
{
//i为根节点
List<TreeNode> ls = helper(m, i-1);//i节点的左子树
List<TreeNode> rs = helper(i+1, n);//i节点的右子树
for(TreeNode l : ls)
{
for(TreeNode r : rs)
{
TreeNode curr = new TreeNode(i);
curr.left = l;
curr.right = r;
res.add(curr);
}
}
}
return res;
}
}