Question

Formatted question description: https://leetcode.ca/all/95.html

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]


Example 2:

Input: n = 1
Output: [[1]]


Constraints:

• 1 <= n <= 8

Algorithm

This kind of tree building problem is generally solved by recursion, and this problem is no exception, dividing the left and right subtrees, and recursive construction.

This actually uses the well-known divide and conquer method Divide and Conquer, and similar problems are the same as the previous Different Ways to Add Parentheses method, using recursion to solve, dividing the left and right sub-arrays, recursive construction.

At the beginning, consider the interval [1, n] as a whole, and then you need to treat each number as the root node, which divides the left and right sub-intervals, and then call the recursive function separately, you will get two Node array, the next thing to do is to take one node each time from these two arrays, as the left and right child nodes of the current root node, and then add the root node to the result array.

Pitfalls

1. When start>end, if you directly return an empty list, size=0, then inserting the left and right subtrees will not work, i=0, i<left.size() loop will not enter So I use if-else to determine whether the list is empty So you must add a null to the list, let size=1

2. To create a root node, it must be in two for loops, because each time is an independent tree. I created the root node first, and then went into the for loop, but the result was repeated, because each for was operated on the same tree, and the added tree was changed.

I thought of the idea of creating left and right subtrees, but I didn’t figure out how to implement it and how to return the built subtrees to the upper level. This generate(start, end) is great.

Code

• import java.util.ArrayList;
import java.util.List;

public class Unique_Binary_Search_Trees_II {

public static void main(String[] args) {
Unique_Binary_Search_Trees_II out = new Unique_Binary_Search_Trees_II();
Solution s = out.new Solution();

for (TreeNode each: s.generateTrees(3)) {
System.out.println(each);
}
}

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

// optimized
public class Solution {

public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new ArrayList<TreeNode>();
}

return generate(1, n);
}

public ArrayList<TreeNode> generate(int start, int end) {

ArrayList<TreeNode> result = new ArrayList<TreeNode>();

if (start > end) {
return result;
}

for (int i = start; i <= end; i++) {

// i as root
ArrayList<TreeNode> left = generate(start, i - 1);
ArrayList<TreeNode> right = generate(i + 1, end);

// append left subtree and right subtree
// @note@note: should put inside for looping!, or, reference is modified onstantly!
for (TreeNode l : left) {
for (TreeNode r : right) {

// 每次都要复制一个
TreeNode currentRoot = new TreeNode(i); // 当前的i作为head node

currentRoot.left = l;
currentRoot.right = r;

}
}
}

return result;
}

}

// DP version
public class Solution_iterative {

public List<TreeNode> generateTrees(int n) {

if (n == 0) {
return new ArrayList<TreeNode>();
}

@SuppressWarnings("unchecked")
List<TreeNode>[] result = new ArrayList[n + 1]; // @note: just like: new int[10]

result[0] = new ArrayList<TreeNode>(); // empty tree

for (int i = 1; i <= n; i++) {
result[i] = new ArrayList<TreeNode>(); // store all combinations when n is i

for (int leftIndex = 0; leftIndex < i; leftIndex++) {
for (TreeNode leftSub : result[leftIndex]) { // get ONE left subtree
for (TreeNode rightSub : result[i - leftIndex - 1]) { // get One right subtree
TreeNode tmpRoot = new TreeNode(leftIndex + 1);
tmpRoot.left = leftSub;

// @note:@memorize: key is here. should generate right subtree, where the start number is "1 + leftIndex"
tmpRoot.right = clone(rightSub, leftIndex + 1);
}
}
}
}
return result[n];
}

// apply offset is still a local recursion
private TreeNode clone(TreeNode n, int offset) { // name is nice, self-explanatory

if (n == null) return null;
TreeNode node = new TreeNode(n.val + offset);
node.left = clone(n.left, offset);
node.right = clone(n.right, offset);
return node;
}

}
}

############

/**
* 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;
*     }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
return generateTrees(1, n);
}

private List<TreeNode> generateTrees(int left, int right) {
List<TreeNode> ans = new ArrayList<>();
if (left > right) {
} else {
for (int i = left; i <= right; ++i) {
List<TreeNode> leftTrees = generateTrees(left, i - 1);
List<TreeNode> rightTrees = generateTrees(i + 1, right);
for (TreeNode l : leftTrees) {
for (TreeNode r : rightTrees) {
TreeNode node = new TreeNode(i, l, r);
}
}
}
}
return ans;
}
}

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def gen(left, right):
ans = []
# this if check instead of if left==right then return Node(left), less hassle
if left > right:
ans.append(None)
else:
# right+1, to cover case when left==right
for i in range(left, right + 1):
left_trees = gen(left, i - 1)
right_trees = gen(i + 1, right)
for l in left_trees:
for r in right_trees:
node = TreeNode(i, l, r)
ans.append(node)
return ans

return gen(1, n)

############

class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""

def clone(root, offset):
if root:
newRoot = TreeNode(root.val + offset)
left = clone(root.left, offset)
right = clone(root.right, offset)
newRoot.left = left
newRoot.right = right
return newRoot

if not n:
return []
dp = [[]] * (n + 1)
dp[0] = [None]
for i in range(1, n + 1):
dp[i] = []
for j in range(1, i + 1):
for left in dp[j - 1]:
for right in dp[i - j]:
root = TreeNode(j)
root.left = left
root.right = clone(right, j)
dp[i].append(root)
return dp[-1]


• /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
return gen(1, n);
}

vector<TreeNode*> gen(int left, int right) {
vector<TreeNode*> ans;
if (left > right) {
ans.push_back(nullptr);
} else {
for (int i = left; i <= right; ++i) {
auto leftTrees = gen(left, i - 1);
auto rightTrees = gen(i + 1, right);
for (auto& l : leftTrees) {
for (auto& r : rightTrees) {
TreeNode* node = new TreeNode(i, l, r);
ans.push_back(node);
}
}
}
}
return ans;
}
};

• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
var gen func(left, right int) []*TreeNode
gen = func(left, right int) []*TreeNode {
var ans []*TreeNode
if left > right {
ans = append(ans, nil)
} else {
for i := left; i <= right; i++ {
leftTrees := gen(left, i-1)
rightTrees := gen(i+1, right)
for _, l := range leftTrees {
for _, r := range rightTrees {
node := &TreeNode{i, l, r}
ans = append(ans, node)
}
}
}
}
return ans
}

return gen(1, n)
}

• /**
* Definition for a binary tree node.
* class TreeNode {
*     val: number
*     left: TreeNode | null
*     right: TreeNode | null
*     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.left = (left===undefined ? null : left)
*         this.right = (right===undefined ? null : right)
*     }
* }
*/

function generateTrees(n: number): Array<TreeNode | null> {
if (n == 0) return [];
return helper(1, n);
}

function helper(start: number, end: number): Array<TreeNode | null> {
let ans = [];
if (start > end) {
ans.push(null);
return ans;
}
for (let i = start; i <= end; i++) {
let lefts = helper(start, i - 1);
let rights = helper(i + 1, end);
for (let left of lefts) {
for (let right of rights) {
let root = new TreeNode(i, left, right);
ans.push(root);
}
}
}
return ans;
}