leetcode: 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

原问题链接：https://leetcode.com/problems/unique-binary-search-trees/

 

问题分析

　　这个问题的难点在于要找到一个递归的关系来描述它。对于给定n个节点的二叉搜索树来说，它到底有多少种构成情况呢？我们先从一些最初始的情况来看。

　　当只有0个和1个节点的情况下，肯定构成的二叉搜索树数量是1。当有2个节点的时候呢？它主要的构成如下图：

　　如果对上述的问题更加一般化，对于一个长度为i的串来说，当要求它所有可能构成的二叉搜索树的话，它可能的构成是有这个串里每个节点都是根节点的所有情况。先假定里面取节点j的情况来看，它将是一个如下图的情况：

　　在上图中，我们可以看到在以节点j作为根节点的情况下，它的左子树对应着前面这个问题里f(0, i) 的子问题f(0, j - 1)，它的右子树对应着这个问题里的子问题f(j + 1, i)。那么对于以j为根节点的情况它所有可能的子树的数量则是两个子树的可能数量的乘积，也就是说f(0, i) = f(0, j - 1) * f(j + 1, i)。

　　这里仅仅是对应一个节点为根的情况。在实际的情况中，我们是每个节点都可能为根节点，所以应该是它们每个节点为根的情况的数量的求和。

　　用递归的方式表达的话就是f(n) = sum(f(i) * f(n - i - 1)) (i = 1, ... n)。　同时我们也有了初始条件f(0) = f(1) = 1。

　　在具体的实现里，我们可以考虑用到动态规划的思路，我们创建一个长度为n + 1的数组int[] nums = new int[n + 1];　最开始的nums[0] = 1表示没有元素的时候，可以构造的二叉搜索树的数量是1，同样nums[1] = 1，剩下的就是基于这个去递推的计算。

　　按照上述的思路，可以得到详细的实现代码如下：

 

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