Sponsored
Sponsored
This approach involves dividing the set of integers from 1 to n into left and right subtrees recursively for each possible root value. For each possible root node, the values less than the root form the left subtree and the values greater than the root form the right subtree. We repeat this process recursively to construct all unique BSTs by selecting each number in the range as the root.
Time Complexity: O(4^n / √n) where n is the number of nodes because it involves generating all unique trees which is a Catalan number problem.
Space Complexity: O(4^n / √n) for storing the results.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7def generate_trees(start, end):
8 if start > end:
9 return [None]
10 all_trees = []
11 for i in range(start, end + 1):
12 left_trees = generate_trees(start, i - 1)
13 right_trees = generate_trees(i + 1, end)
14 for l in left_trees:
15 for r in right_trees:
16 current_tree = TreeNode(i)
17 current_tree.left = l
18 current_tree.right = r
19 all_trees.append(current_tree)
20 return all_trees
21
22def generate_trees_main(n):
23 if n == 0:
24 return []
25 return generate_trees(1, n)
26This Python code defines a TreeNode class and a recursive function 'generate_trees' that builds all unique BSTs for integers between 'start' and 'end'. It selects each number as the root and recursively builds left and right subtrees.
This approach involves leveraging dynamic programming to store results of previously evaluated subproblems to optimize the recursive solution. We maintain a memoization table to store precalculated trees for specific ranges, aiding efficient calculation by reducing the re-computation of the same subproblems.
Time Complexity: O(4^n / √n) due to solving subproblems exactly once.
Space Complexity: O(4^n / √n) for storing the memoized results.
1class TreeNode:
2 def
This Python code employs memoization via the 'lru_cache' decorator to efficiently store and reuse the results of previously computed subproblems within the recursive 'generate_trees' function.