Description
https://leetcode.com/problems/unique-binary-search-trees/
Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3 Output: 5
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 19
Explanation
For 0 <= i <= n, all values less than i go to the left tree, all values greater than i go to the right tree. Count how many possible ways to build a left tree and how many possible ways to build a right tree, and multiply the count to get the result.
Python Solution
class Solution:
def numTrees(self, n: int) -> int:
results = {
0: 1,
1: 1,
2: 2
}
return self.helper(n, results)
def helper(self, n , results):
if n in results:
return results[n]
else:
result = 0
for i in range(n):
result += self.helper(i, results) * self.helper(n - i - 1, results)
results[n] = result
return result
- Time Complexity: O(N^2).
- Space Complexity: O(N).
I found that solution very popular and helpful:
https://www.youtube.com/watch?v=ElV3nrMaso8&ab_channel=EricProgramming