Given 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

 

/** * Definition for binary tree * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; left = null; right = null; } * } */

 

public class Solution {	public ArrayList
    
      generateTree(int start, int end) {		ArrayList
     
       result = new ArrayList
      
       ();		if (start > end) {			result.add(null);			return result;		}		ArrayList
       
         leftTree = new ArrayList
        
         ();		ArrayList
         
           rightTree = new ArrayList
          
           (); for (int i = start; i <= end; i++) { //从start到end，选取每一个数尝试构造BST leftTree = generateTree(start, i-1); //取小于i的数构造i的左子树 rightTree = generateTree(i+1, end); //取大于i的数构造i的右子树，以此来保证i的二叉查找树有序性 for (int j = 0; j < leftTree.size(); j++) { for (int k = 0; k < rightTree.size(); k++) { //取i作为root构造BST，共有num_left*num_right种方式 TreeNode curNode = new TreeNode(i + 1); curNode.left = leftTree.get(j); //left、right是递归得到的root的集合，相当于list的每个节点都是一颗二叉查找树 curNode.right = rightTree.get(k); //将每一种可能的组合，接到当前的root(i)上组成一颗BST result.add(curNode); } } } return result; } //主调用函数：返回的List是每一棵树的root的集合，List.length = n的二叉搜索树的个数 public ArrayList
           
             generateTrees(int n) { return generateTree(0, n-1); }}