LeetCode | 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

对树的操作一般都是递归了，这里在实现的时候的一个技巧就是，越界时将null作为一个元素插入数组，既可以简化代码，又可以通过n=0时候的测试 = = ！

代码

import java.util.ArrayList;

public class UniqueBinarySearchTreesII {
	public ArrayList<TreeNode> generateTrees(int n) {
		return solve(1, n);
	}

	private ArrayList<TreeNode> solve(int low, int high) {
		ArrayList<TreeNode> list = new ArrayList<TreeNode>();
		if (low > high) {
			list.add(null);
			return list;
		}
		for (int i = low; i <= high; ++i) {
			ArrayList<TreeNode> leftList = solve(low, i - 1);
			ArrayList<TreeNode> rightList = solve(i + 1, high);
			TreeNode root = null;
			for (TreeNode left : leftList) {
				for (TreeNode right : rightList) {
					root = new TreeNode(i);
					root.left = left;
					root.right = right;
					list.add(root);
				}
			}
		}
		return list;
	}
}

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

LeetCode | Unique Binary Search Trees II

原文：http://blog.csdn.net/perfect8886/article/details/20395757