不同的二叉搜索树

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例：

Code

输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

### 解题思路

一开始没有想到左子树和右子树如何创建。

主要是先找到根节点，然后通过根节点生成左边的子树列表，以及右边子树列表。

左边子数列表的思路：递归求解，将左边子树中的值每个都作为根节点计算。

### 代码

```*java*

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode() {}

* TreeNode(int val) { this.val = val; }

* TreeNode(int val, TreeNode left, TreeNode right) {

* this.val = val;

* this.left = left;

* this.right = right;

* }

class Solution {

public List Treess(int st, int ed){

ArrayList list = new ArrayList();

if(st>ed){

list.add(null);

return list;

}

for(int i=st;i<=ed;i++){

List left = Treess(st, i-1);

List right = Treess(i+1, ed);

for(TreeNode l:left){

for(TreeNode r:right){

TreeNode root = new TreeNode(i);

root.left = l;

root.right = r;

list.add(root);

}

return list;

}

public List generateTrees(int n) {

if(n==0){

return new ArrayList();

}

return Treess(1, n);

}

```