Unique Binary Search Trees II

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

Solution: to generate all unique BSTs, we should generate the root from 1 to n, and generate its left subtree from 0 to i-1 and for each left subtree, we generate the right subtree from i+1 to n recursively. Note: this is a Binary Search Tree, so that we must make sure that all nodes whose values are smaller than root must be in the left subtree of the root, and all nodes whose values are larger than root must be in the right subtree of the root.

Java语言: UniqueBinarySearchTreesII

01 public ArrayList<TreeNode> generateTrees(int n) {
02     ArrayList<Integer> num=new ArrayList<Integer>();
03     for(int i=1;i<=n;i++)
04     {
05         num.add(i);
06     }
07     return generateTree(num,0,n-1);
08 }
09 
10 public ArrayList<TreeNode> generateTree(ArrayList<Integer> num, int start, int end)
11 {
12     ArrayList<TreeNode> results=new ArrayList<TreeNode>();
13     if(start>end)
14     {
15         TreeNode n=null;          
16         results.add(n);
17         return results;
18     }
19     for(int i=start;i<=end;i++)
20     {
21         ArrayList<TreeNode> leftTrees=generateTree(num, start, i-1);
22         for(int j=0;j<leftTrees.size();j++)
23         {
24             TreeNode leftChild=leftTrees.get(j);
25             ArrayList<TreeNode> rightTrees=generateTree(num, i+1, end);
26             for(int k=0;k<rightTrees.size();k++)
27             {
28                 TreeNode rightChild=rightTrees.get(k);
29                 TreeNode root=new TreeNode(num.get(i));
30                 root.left=leftChild;
31                 root.right=rightChild;
32                 results.add(root);
33             }
34         }
35     }
36     return results;
37 }