# 0095. Unique Binary Search Trees II
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/unique-binary-search-trees-ii/
## 思路
**二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树**。因此在生成所有可行的二叉搜索树的时候，假设当前序列长度为 nn，如果我们枚举根节点的值为 ii，那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 [1…i−1]，右子树的节点值的集合为 [i+1…n]。**而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题，因此我们可以想到用回溯的方法来解决这道题目。**

我们定义 generateTrees(start, end) 函数表示当前值的集合为 [start,end]，返回序列 [start,end] 生成的所有可行的二叉搜索树。按照上文的思路，我们考虑枚举 [start,end] 中的值 ii 为当前二叉搜索树的根，那么序列划分为了[start,i−1] 和 [i+1,end] 两部分。我们递归调用这两部分，即 generateTrees(start, i - 1) 和 generateTrees(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

## Java Code

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0){
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1,n);
    }
    public List<TreeNode> generateTrees(int start, int end){
        List<TreeNode> ans = new LinkedList<TreeNode>();
        if(start > end){
            ans.add(null);
            return ans;
        }
        for(int i = start;i <= end;i++){
            List<TreeNode> leftTree = generateTrees(start, i-1);
            List<TreeNode> rightTree = generateTrees(i+1, end);
            for(TreeNode left:leftTree){
                for(TreeNode right:rightTree){
                    TreeNode currNode = new TreeNode(i);
                    currNode.left = left;
                    currNode.right = right;
                    ans.add(currNode);
                }
            }
        }
        return ans;
    }
}

## Result
Runtime: 1 ms, faster than **91.75%** of Java online submissions for Unique Binary Search Trees II.
Memory Usage: 39.5 MB, less than **65.99%** of Java online submissions for Unique Binary Search Trees II.