**Unique Binary Search Trees II**
Description
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 ... n
.
Example
1 | Input: 3 |
Solution
Unique BST Number(leetcode #96)
This problem is unique BST I
, and it’s to find out the number of unique BST. This solution is a little tricky, I looked at the discussion part because I have no thought about it. The solution impressed me a lot, using Dynamic Programming. So how? We traverse every node from 1 to n, and every node should have the chance to be the root node, so when this node is root, how many unique BST do we have ? The answer is (unique BST combined with left) * (unique BST combined with right). BUT there is nothing to do with DP, let us see, (1, 2, 3) has the same number unique BST as (3, 4, 5). So when we try to calculate the right part, we have already know it. The following algorithm will be more straightforward.
Algorithm
Python
1 | def numTrees(self, n): |
Complexity
- Time Complexity: O(N^2)
- Space Complexity: O(N)
Unique BST root
Now the current problem is to have all the unique BST, based on the way to calculate number, we can come up with a similar thought, that is we have the current root, then combine all the left with all the right part. This can be done recursively.
Algorithm
Python
1 | def generateTrees(n): |