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 <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct TreeNode* createNode(int val) {
11 struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
12 newNode->val = val;
13 newNode->left = NULL;
14 newNode->right = NULL;
15 return newNode;
16}
17
18struct TreeNode** generateTrees(int start, int end, int* returnSize) {
19 struct TreeNode** allTrees = (struct TreeNode**)malloc(1000 * sizeof(struct TreeNode*));
20 if (start > end) {
21 *returnSize = 1;
22 allTrees[0] = NULL;
23 return allTrees;
24 }
25 int size = 0;
26 for (int i = start; i <= end; ++i) {
27 int leftSize = 0, rightSize = 0;
28 struct TreeNode** leftTrees = generateTrees(start, i - 1, &leftSize);
29 struct TreeNode** rightTrees = generateTrees(i + 1, end, &rightSize);
30 for (int l = 0; l < leftSize; ++l) {
31 for (int r = 0; r < rightSize; ++r) {
32 struct TreeNode* root = createNode(i);
33 root->left = leftTrees[l];
34 root->right = rightTrees[r];
35 allTrees[size++] = root;
36 }
37 }
38 }
39 *returnSize = size;
40 return allTrees;
41}
42
43struct TreeNode** generateTreesMain(int n, int* returnSize) {
44 if (n == 0) {
45 *returnSize = 0;
46 return NULL;
47 }
48 return generateTrees(1, n, returnSize);
49}
50This C code uses a recursive divide-and-conquer approach to generate unique BSTs. It uses a helper function that builds trees by choosing each number as a root and constructing 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.
1import java.util.*;
2
This Java code implements memoization using a HashMap to cache results of recursive subproblem solutions, optimizing performance by reducing redundant evaluations.