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
confused what "{1,#,2,3}"
means?
Have you met this question in a real interview?
Solution:
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; left = null; right = null; } 8 * } 9 */10 public class Solution {11 public ListgenerateTrees(int n) {12 List list = generateTreesRecur(n,1,n);13 return list;14 15 }16 17 public List generateTreesRecur(int len, int s, int e){18 List treeList = new ArrayList ();19 if (len==0){20 treeList.add(null);21 return treeList;22 }23 24 if (len==1){25 TreeNode newNode = new TreeNode(s);26 treeList.add(newNode);27 return treeList;28 }29 30 for (int i=s;i<=e;i++){31 int leftLen = i-s;32 int rightLen = e-i;33 List leftList = generateTreesRecur(leftLen,s,i-1);34 List rightList = generateTreesRecur(rightLen,i+1,e);35 for (int j=0;j