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.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11vector<TreeNode*> generateTrees(int start, int end) {
12 if (start > end) return {NULL};
13 vector<TreeNode*> allTrees;
14 for (int i = start; i <= end; ++i) {
15 vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
16 vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
17 for (auto left : leftTrees) {
18 for (auto right : rightTrees) {
19 TreeNode* root = new TreeNode(i);
20 root->left = left;
21 root->right = right;
22 allTrees.push_back(root);
23 }
24 }
25 }
26 return allTrees;
27}
28
29vector<TreeNode*> generateTrees(int n) {
30 if (n == 0) return {};
31 return generateTrees(1, n);
32}
33This C++ solution creates a recursive function to produce all unique BSTs. It makes use of the TreeNode struct to construct trees, selecting each node in a range as the root and building left and right subtrees recursively.
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.