[
tree
dp
divide and conquer
]
Leetcode 0095 Unique Binary Search Trees II
Problem statement
https://leetcode.com/problems/unique-binary-search-trees-ii/
Solution
We can use dp
technique here, where in dp[i][j]
we keep all possible trees from numbers i ... j
. We can also keep only one dimensional dp
, but then we need to clone
trees, adding the same values to all elements. However, number of trees is exponential, and I think it is not worth to make this optimization from O(n^2)
to O(n)
memory, because problem can be solved for only small n <= 50
.
Complexity
Time and space complexity is O(C_{2n}^n)
approximately, because we have Catalan number of trees.
Code
class Solution:
def generateTrees(self, n):
def dp(i, j):
if i > j: return [None]
ans = []
for k in range(i, j + 1):
for lft, rgh in product(dp(i, k-1), dp(k+1, j)):
root = ListNode(k)
root.left = lft
root.right = rgh
ans.append(root)
return ans
return dp(1, n)