题目链接：https://leetcode.com/problems/unique-binary-search-trees-ii/description/
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这道题是求解所有可行的二叉查找树，在Unique Binary Search Trees中，二叉查找树的数目是卡塔兰数，在上一题中我们采用的方法存储所有子问题的解，存储G（1）…G(n-1),再求解G(n)，如此题采用这种方式会浪费很多空间，因此我们采用循环中调用递归函数求解子问题。思路是：每次选取一个结点作为根，然后递归求解左右子树的结果，然后将左右子树的结果进行匹配，若左子树有p种，右子树有q种，则以i为根的BST有p*q种，将每个结点作为根的所有结果都加入集合后，再返回结果。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<TreeNode> generateTrees(int n) { if(n<1) return new ArrayList<>(); return CreateBST(1, n); } public List<TreeNode> CreateBST(int left,int right){ List<TreeNode> res=new ArrayList<>(); if(left>right){ res.add(null); //加入一棵空树； return res; } for(int i=left;i<=right;i++){ //i代表以i为根的BST List<TreeNode> leftList=CreateBST(left,i-1); //存储左子树 List<TreeNode> rightList=CreateBST(i+1,right); //存储右子树 for(int j=0;j<leftList.size();j++){ for(int k=0;k<rightList.size();k++){ TreeNode root=new TreeNode(i); root.left=leftList.get(j); root.right=rightList.get(k); res.add(root); } } } return res; } }