[leetcode] Unique Binary Search Trees II

一个发现是可以add null到arraylist里面的.. 以后要试下其他java data structure可不可以
另外一个是其实这种解法return 的结果 有大量subtree是共享的.. 可以写个copy tree来clone每个subtree.. 但感觉时间空间太大了。。不一定是面试想要的..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

public class Solution { public List<TreeNode> generateTrees(int n) { return generateRec(1,n); } private List<TreeNode> generateRec(int start, int end){ List<TreeNode> result = new ArrayList<TreeNode>(); if (start > end){ result.add(null); return result; } for (int i = start; i <= end; i++){ List<TreeNode> left = generateRec(start, i-1); List<TreeNode> right = generateRec(i+1, end); for (int j = 0; j < left.size(); j++){ for (int k = 0; k < right.size(); k++){ TreeNode root = new TreeNode(i); root.left = left.get(j); root.right = right.get(k); result.add(root); } } } return result; } }