LeetCode-----Unique Binary Search Trees II

需要将所有的二叉搜索树都构建出来，思路还是跟前面1的一样，找到一个数作为根结点，剩余的数分别划入左子树或者右子树，用递归来实现。

实例代码如下：

package com.zhumq.lianxi;

import java.util.ArrayList;
import java.util.List;

public class UniqueBinarySearchTreeII {
    //定义TreeNode
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    // Unique Binary Search Trees II
    // 时间复杂度TODO，空间复杂度TODO
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
            return generate(1, n);
    } 

    private static List<TreeNode > generate(int start, int end) {
        List<TreeNode> subTree = new ArrayList<>();
        if (start > end) {
            subTree.add(null);
            return subTree;
        } 
        for (int k = start; k <= end; k++) {
            //递归构建左子树
            List<TreeNode> leftSubs = generate(start, k - 1);
            //递归构建右子树
            List<TreeNode> rightSubs = generate(k + 1, end);
            //构造所有可能的树
            for (TreeNode i : leftSubs) {
                for (TreeNode j : rightSubs) {
                    TreeNode node = new TreeNode(k);
                    node.left = i;
                    node.right = j;
                    subTree.add(node);
                }
            }
        } 
        return subTree;
    }
}