[leetcode]Unique Binary Search Trees

Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

递归：

 

/*
设count[1,n]表示1~n可以组成的BST的个数。
num[i] 表示以i为根的BST个数，有num[i] = count[1,i-1]*count[i+1,n];
count[1,n] = sum(num[i]);
*/

public class Solution {
    public int numTrees(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
       if(n<1) return 0;
       return count(1,n); 
    }
    
    public int count(int start,int end){
        if(start == end) return 1;
        int count = count(start+1,end);
        count = count+count(start,end-1);
        for(int i = start+1;i<=end-1;i++){
            count = count+count(start,i-1)*count(i+1,end);
        }
        return count;
    }
}

 Unique Binary Search Trees II

 

Aug 27 '123664 / 10952

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

与上题相比，需要输出所有符合条件的树的具体形式：

/*集合的笛卡尔乘积*/
public class UniqueBinaryTree2 {
	 
	    public ArrayList<TreeNode> generateTrees(int n) {
	        // Start typing your Java solution below
	        // DO NOT write main() function
	        return generateTrees(1,n);
	    }
	    
	    public ArrayList<TreeNode> generateTrees(int start,int end){ 
	    	ArrayList<TreeNode> result = new ArrayList<TreeNode>();
	    	if(start>end) {result.add(null);return result;}
	        for(int i = start;i<=end;i++){
	            ArrayList<TreeNode> lefts = generateTrees(start,i-1);
	            ArrayList<TreeNode> rights = generateTrees(i+1,end); 
	            for (int j = 0; j < lefts.size(); ++j) {
	                for (int k = 0; k < rights.size(); ++k) {
	                    TreeNode root = new TreeNode(i);
	                    root.lchild = lefts.get(j);
	                    root.rchild = rights.get(k);
	                    result.add(root);
	                }
	            }
	          
	        }
	        return result;
	    }
}