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
  
    generateTrees(int n) {
		return solve(1, n);
	}

	private ArrayList
   
     solve(int low, int high) { ArrayList
    
      list = new ArrayList
     
      (); if (low > high) { list.add(null); return list; } for (int i = low; i <= high; ++i) { ArrayList
      
        leftList = solve(low, i - 1); ArrayList
       
         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; } }