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
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; left = null; right = null; } * } */ public class Solution { public ArrayList<TreeNode> generateTrees(int n) { // Start typing your Java solution below // DO NOT write main() function return get(1,n); } public ArrayList<TreeNode> get(int s,int e){ ArrayList<TreeNode> res= new ArrayList<TreeNode>(); if(s>e) {res.add(null);return res;} for(int i=s;i<=e;i++){ ArrayList<TreeNode> l=get(s,i-1); ArrayList<TreeNode> r=get(i+1,e); for(int m=0;m<l.size();m++){ for(int n=0;n<r.size();n++){ TreeNode c= new TreeNode(i); c.left=l.get(m); c.right=r.get(n); res.add(c); }} } return res; } }