Open huimeich opened 8 years ago
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<TreeNode> generateTrees(int n) {
return genTree(1, n);
}
public List<TreeNode> genTree(int start, int end) {
List<TreeNode> parents = new ArrayList<TreeNode>();
if (start > end) return parents;
for (int i = start; i <= end; i++) {
List<TreeNode> lefts = genTree(start, i - 1);
List<TreeNode> rights = genTree(i + 1, end);
for (int left = 0; left < Math.max(1,lefts.size()); left++){
for (int right = 0; right < Math.max(1,rights.size()); right++){
TreeNode curr = new TreeNode(i);
if (lefts.size() != 0) curr.left = lefts.get(left);
if (rights.size() != 0) curr.right = rights.get(right);
parents.add(curr);
}
}
}
return parents;
}
}
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.