95 Unique Binary Search Trees II
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
@tag-tree
@tag-divideconquer

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

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

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.