[leecode]Unique Binary Search Trees II

新博文地址：[leetcode]Unique Binary Search Trees II

 

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

 这道题看起来真的挺唬人的。但是搞明白之后还算好，提示中说用DP，但是还是用了DFS，总是感觉DP没法做，可能还是DP不熟吧。

思想是模拟人工建树的过程：

首先，一个节点时，已经好了。

n个节点时候（n > 1），第一个节点的左子树一定为空，同理最后一个节点的右子树一定为空。那么中间节点呢，假设中间节点为k（1<k<n），1~k-1是其左子树，k+1~n是其右子树，然后递归实现1~k-1和k+1~n，典型的分治策略。

	List<TreeNode> result = new ArrayList<TreeNode>();
	public List<TreeNode> generateTrees(int n) {
		if (n <= 0) {
		    result.add(null);//坑爹啊，非要加个null，加你妹啊！！！
			return result;
		}
		return  generateSubTree(1, n);
	}

	private List<TreeNode> generateSubTree(int begin,int end) {
		if (begin == end) {
			List<TreeNode> leaf = new ArrayList<TreeNode>();
			leaf.add(new TreeNode(begin));
			return leaf;
		}
		List<TreeNode> list = new ArrayList<TreeNode>();
		for (int i = begin; i <= end; i++) {
			if (i == begin) {
				List<TreeNode> right = generateSubTree(i + 1, end);
				for (TreeNode tem : right) {
					TreeNode node = new TreeNode(i);
					node.right = tem;
					list.add(node);
				}
			} else if (i == end) {
				List<TreeNode> left = generateSubTree( begin, end - 1);
				for (TreeNode tem : left) {
					TreeNode node = new TreeNode(i);
					node.left = tem;
					list.add(node);
				}
			} else {
				List<TreeNode> left = generateSubTree( begin, i - 1);
				List<TreeNode> right = generateSubTree( i + 1, end);
				for (TreeNode temLeft : left) {
					for (TreeNode temRight : right) {
						TreeNode node = new TreeNode(i);
						node.left = temLeft;
						node.right = temRight;
						list.add(node);
					}
				}
			}
		}
		return list;
	}

 我去，看了别人的代码，貌似都是清一色的分治法，只不过人家的代码简洁多了，果然自己是渣渣