Problem
Given an integer 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
Solution 1
using recursion,
/**
* 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) {
List<TreeNode> result = new ArrayList<TreeNode>();
if(n==0){
return result;
}
return buildTrees(1,n);
}
public List<TreeNode> buildTrees(int start, int end){
List<TreeNode> result = new ArrayList<TreeNode>();
if(start>end ){
result.add(null);
return result;
}
List<TreeNode> rightTrees = new ArrayList<TreeNode>();
List<TreeNode> leftTrees = new ArrayList<TreeNode>();
// pick up a root
for(int i = start; i <= end; i++){
// since i is root, left tree would be from start -> i-1
leftTrees = buildTrees(start, i-1);
// right trees would be from i+1 to end
rightTrees = buildTrees(i+1,end);
// generate trees
for(TreeNode leftTree : leftTrees){
for(TreeNode rightTree: rightTrees){
TreeNode tree = new TreeNode(i);
tree.left = leftTree;
tree.right = rightTree;
result.add(tree);
}
}
}
return result;
}
}
the result :
notice the above solution doesn’t use memorization
Solution 2 (with memorization)
/**
* 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) {
List<TreeNode> result = new ArrayList<TreeNode>();
if(n==0){
return result;
}
return buildTrees(1,n);
}
public List<TreeNode> buildTrees(int start, int end){
List<TreeNode> result = new ArrayList<TreeNode>();
Map<String,List<TreeNode>> hashMap = new HashMap<>();
StringBuilder sb = new StringBuilder();
sb.append(start).append("-").append(end);
if(hashMap.get(sb.toString())!=null){
return hashMap.get(sb.toString());
}
if(start>end ){
result.add(null);
return result;
}
List<TreeNode> rightTrees = new ArrayList<TreeNode>();
List<TreeNode> leftTrees = new ArrayList<TreeNode>();
// pick up a root
for(int i = start; i <= end; i++){
// since i is root, left tree would be from start -> i-1
leftTrees = buildTrees(start, i-1);
// right trees would be from i+1 to end
rightTrees = buildTrees(i+1,end);
// generate trees
for(TreeNode leftTree : leftTrees){
for(TreeNode rightTree: rightTrees){
TreeNode tree = new TreeNode(i);
tree.left = leftTree;
tree.right = rightTree;
result.add(tree);
}
}
}
hashMap.put(sb.toString(),result);
return result;
}
}
I use sart - end
as key, List<TreeNode>
as values to memorize the results
but the performance is even worse. I believe this is caused by the small number of test cases.