96. Unique Binary Trees
https://leetcode.com/problems/unique-binary-search-trees
Considering
Pickup i
as the root node, then:
Left sub-tree: numTrees(i-1) Right sub-tree: numTrees(n-i)
And the possible permutations will be the product of left * right, which is
Python
class Solution:
def __init__(self):
self.memory = {}
def numTrees(self, n):
if n in self.memory:
return self.memory[n]
if n in (0, 1):
return 1
ans = 0
for i in range(1, n + 1):
left = self.numTrees(i - 1)
right = self.numTrees(n - i)
ans += left * right
self.memory[n] = ans
return ans