95. Unique Binary Search Trees II (Medium)
https://leetcode.com/problems/unique-binary-search-trees-ii/
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
Example:
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: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
Solutions
class Solution {
// The straight forward solution is firstly sort out all the possible tree patterns. Then for each tree,
// populate the values by inorder traversal.
int val = 1;
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new ArrayList<>();
}
// First get all the patterns of trees
List<TreeNode> ans = recurse(n);
for (TreeNode node : ans) {
// every time reset the val count
val = 1;
// Inorder traversal and set the values
setValue(node);
}
return ans;
}
private void setValue(TreeNode root) {
if (root == null) {
return;
}
setValue(root.left);
root.val = val++;
setValue(root.right);
}
private List<TreeNode> recurse(int n) {
if (n == 0) {
return null;
}
List<TreeNode> ans = new ArrayList<>();
if (n == 1) {
ans.add(new TreeNode(0));
return ans;
}
for (int i = 0; i < n; i++) {
// left i nodes
List<TreeNode> left = recurse(i);
// right n - i - 2 nodes
List<TreeNode> right = recurse(n - i - 1);
// combine the left and right branch
combine(left, right, ans);
}
return ans;
}
private void combine(List<TreeNode> left, List<TreeNode> right, List<TreeNode> ans) {
// Technically, below situation will never happen
if (left == null && right == null) {
return;
}
// if left == null
if (left == null) {
for (TreeNode node : right) {
TreeNode root = new TreeNode(0);
root.left = null;
root.right = node;
ans.add(root);
}
return;
}
// if right == null
if (right == null) {
for (TreeNode node : left) {
TreeNode root = new TreeNode(0);
root.left = node;
root.right = null;
ans.add(root);
}
return;
}
// if left != null && right != null
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
ans.add(root);
}
}
}
}