Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Constraints
Approach
Links
YouTube
Examples
Input: 3
Output:
[
[1, null, 3, 2],
[3, 2, null, 1],
[3, 1, null, null, 2],
[2, 1, 3],
[1, null, 2, null, 3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
Solutions
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if(n < 1) {
return Collections.EMPTY_LIST;
}
List<TreeNode>[][] dp = new ArrayList[n+1][n+1];
return generateTrees(1, n, dp);
}
private List<TreeNode> generateTrees(int start,
int end,
List<TreeNode>[][] dp) {
List<TreeNode> allTrees = new ArrayList<TreeNode>();
if(start > end) {
allTrees.add(null);
return allTrees;
}
if(dp[start][end] != null) return dp[start][end];
for(int i = start; i <= end; i++) {
// all possible left subtrees if i is choosen to be a root
List<TreeNode> leftTrees = generateTrees(start, i-1, dp);
// all possible right subtrees if i is choosen to be a root
List<TreeNode> rightTrees = generateTrees(i+1, end, dp);
// connect left and right trees to the root i
for(TreeNode leftTree: leftTrees) {
for(TreeNode rightTree: rightTrees) {
TreeNode currentTree = new TreeNode(i);
currentTree.left = leftTree;
currentTree.right = rightTree;
allTrees.add(currentTree);
}
}
}
dp[start][end] = allTrees;
return allTrees;
}
}
