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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

基本思路：

这题和第一个题的思路如出一辙，将某个数作为根节点，然后前面的数作为左子树，后面的作为右子树，在左子树集合中选出一种，再从右子树集合中选出一种，与根一起构成BST。

	public ArrayList<TreeNode> generateTrees(int n)
	{
		return createTree(1, n);
	}
	
	//将某个数作为跟节点，然后前面的数作为左子树，后面的作为右子树
	public ArrayList<TreeNode> createTree(int start,int end)
	{
		ArrayList<TreeNode> rs  = new ArrayList<TreeNode>();
		if(start>end)
		{
			rs.add(null);
			return rs;
		}
		for(int rootNum = start;rootNum<=end;rootNum++)
		{
			ArrayList<TreeNode> left = createTree(start,rootNum-1);
			ArrayList<TreeNode> right = createTree(rootNum+1, end);
			for(int i = 0;i<left.size();i++)
			{
				for(int j = 0;j<right.size();j++)
				{
					TreeNode root = new TreeNode(rootNum);
					root.left = left.get(i);
					root.right = right.get(j);
					rs.add(root);
				}
			}
		}
		return rs;
	}

	public ArrayList<TreeNode> generateTrees(int n)
	{
		ArrayList<ArrayList<TreeNode>> rs = new ArrayList<ArrayList<TreeNode>>();
		
		for(int i = 1;i<=n;i++)
		{
			ArrayList<TreeNode> list = new ArrayList<TreeNode>();
			if(i==1)
			{
				TreeNode root = new TreeNode(i);
				list.add(root);
				rs.add(list);
			}
			else
			{
				list = insertNode(rs.get(i-2), new TreeNode(i));
				rs.add(list);
			}	
		}
		
		return rs.get(n-1);
	}
	
	//将某个大于树中所有节点的值的节点插入一个树中
	public ArrayList<TreeNode> insertNode(ArrayList<TreeNode> list, TreeNode node)
	{
		ArrayList<TreeNode> rs = new ArrayList<TreeNode>();
		
		for(int i = 0;i<list.size();i++)
		{
			int count = 0;
			int index = count+1;
			TreeNode root = list.get(i);
			TreeNode ro = copyTree(root);
			TreeNode p = ro;
			TreeNode next;
			while(p.right!=null)
			{
				if(index>count)
				{
					next = p.right;
					p.right = node;
					node.left = next;
					rs.add(ro);
					ro = copyTree(root);
					count++;
					index=1;
				}
				else
				{
					p = p.right;
					index++;
				}
			}
			p.right = node;
			rs.add(ro);
			
			//增加n作为头节点
			ro = copyTree(root);
			node.left = ro;
			ro = node;
			rs.add(ro);
		}
		return rs;
	}
	
	//copy一棵树
	public TreeNode copyTree(TreeNode root)
	{
		if(root==null)
			return null;
		else
		{
			TreeNode ro = new TreeNode(root.val);
			ro.left = copyTree(root.left);
			ro.right = copyTree(root.right);
			return ro;
		}
	}

Unique Binary Search Trees II,布布扣,bubuko.com

Unique Binary Search Trees II

原文：http://blog.csdn.net/cow__sky/article/details/22086941