Unique Binary Search Trees 总结

有关unique 二叉搜索树的题目有两个，第一道题目是确定二叉搜索树的个数，第二道题目是输出所有的二叉搜索树，这两道题目属于比较难的题目，对于解决它们的方法也是比较重要的，我们要掌握。

1，Unique Binary Search Trees
给定一个正整数n，确定有多少个不同的二叉搜索树，树的节点取值范围为(1....n)。
例如：给定n = 3，输出为5
   1           3     3      2       1
     \         /     /        / \        \
      3     2     1       1  3       2
     /      /        \                      \
   2      1          2                     3

求解这个问题我们不妨从简单开始分析，我们设定一个数组result来表示n在不同值下有几种不同的二叉树。当n为0时，这时是一颗空树，result[0] = 1; 当n = 1时，只有一种情况，result[1] = 1; 当n = 2 时，两个数可以分别作为根节点，result[2] = 2; 当n = 3时，正如题目给出的结果，result[3] = 5；我们从这里可以发现一些规律，result[n] = result[0] * result[n - 1] + result[1] * result[n -2] + result[n-1] * result[0] (n > 1); 我们会发现这正好符合卡特兰数的递推式，有了递推式我们就很容易的写出代码了，代码如下：

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

2，Unique Binary Search Trees II
给定一个正整数n，输出所有不同的二叉搜索树，数的节点取值范围为(1....n)。
例如：给定n = 3
   1           3     3      2       1
     \         /     /        / \        \
      3     2     1       1  3       2
     /      /        \                      \
   2      1          2                     3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

这道题目比上一道题目要难，要输出所有不同的二叉搜索树，解决树的问题我们首先想到的就是用递归来解决，对于这道题目，我们参考之前介绍过的一道题目Different Ways to Add Parentheses，我们同样在for循环中递归解决子问题，这个方法需要我们通过题目来巩固，代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if(n == 0) return result;
        return generateSubtrees(1, n);
    }
    
    public List<TreeNode> generateSubtrees(int start, int n) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if(start > n) {
            result.add(null);
            return result;
        }
        for(int i = start; i <= n; i++) {
            List<TreeNode> left = generateSubtrees(start, i - 1);
            List<TreeNode> right = generateSubtrees(i + 1, n);
            for(TreeNode leftnode : left)
                for(TreeNode rightnode : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftnode;
                    root.right = rightnode;
                    result.add(root);
                }
        }
        return result;
    }
}