[LeetCode] 95. Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

递归(～o▔▽▔)～o o～(▔▽▔o～)

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public List<TreeNode> generateTrees(int n) {
	if (n < 1) {
	return new ArrayList<>();
	}
	return generateBST(1, n);
	}
	private List<TreeNode> generateBST(int start, int end) {
	List<TreeNode> result = new ArrayList<>();
	if (start > end) {
	result.add(null); // !!!
	return result;
	}
	if (start == end) {
	result.add(new TreeNode(start));
	return result;
	}
	for (int i = start; i <= end; i++) {
	List<TreeNode> leftChildren = generateBST(start, i - 1);
	List<TreeNode> rightChildren = generateBST(i + 1, end);
	for (TreeNode left : leftChildren) {
	for (TreeNode right : rightChildren) {
	TreeNode root = new TreeNode(i);
	root.left = left;
	root.right = right;
	result.add(root);
	}
	}
	}
	return result;
	}
	}

view raw generateTrees2.java hosted with ❤ by GitHub