https://leetcode.com/problems/unique-binary-search-trees/
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
Code
class Solution(object): def numTrees(self, n): """ :type n: int :rtype: int """ if not n: return 0 numOfTrees = [0] * (n+1) # for easier indexing. Using numOfTrees[1:] numOfTrees[0] = 1 for i in xrange(1, n+1): for j in xrange(1, i+1): numOfTrees[i] += numOfTrees[j-1] * numOfTrees[i-j] return numOfTrees[n]
Idea
When you are given `n` (`n` is the size of sorted numbers to be placed in BST), there are multiple ways to construct unique BSTs depending on which element is placed as the root: you can put the first element as the root, then place the remaining `n-1` elements in the right tree. You can put the second element as the root, then place the first element as the left tree and the remaining `n-2` elements in the right tree. So on and so forth.
Therefore, you can use an array, `numOfTrees` in my code, to store the number of unique BSTs. The final result, `numOfTrees[n]`, will be based on `numOfTrees[n’]` where `n’ < n`: You can put 1~n as root. When you put element `i` (`1<=i<=n`) as the root, its left tree can have `numOfTrees[i-1]` different unique ways of construction and its right tree can have `numOfTrees[n-i]` ways of construction. So the total number of unique trees when root equal to `i` is `numOfTrees[i-1] *numOfTrees[n-i]`.
A more mathematical way is to directly solve this problem using Catalan Number. Then you only need O(N) time and O(1) space. Please find introduction to Catalan Number below: