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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<TreeNode> GenerateTrees(int n) {
13 if (n == 0) return new List<TreeNode>();
14 return GenerateTrees(1, n);
15 }
16
17 private IList<TreeNode> GenerateTrees(int start, int end) {
18 IList<TreeNode> allTrees = new List<TreeNode>();
19 if (start > end) {
20 allTrees.Add(null);
21 return allTrees;
22 }
23
24 for (int i = start; i <= end; i++) {
25 var leftTrees = GenerateTrees(start, i - 1);
26 var rightTrees = GenerateTrees(i + 1, end);
27 foreach (var left in leftTrees) {
28 foreach (var right in rightTrees) {
29 TreeNode root = new TreeNode(i);
30 root.left = left;
31 root.right = right;
32 allTrees.Add(root);
33 }
34 }
35 }
36 return allTrees;
37 }
38}
39This C# solution applies the recursive approach to generate all possible configurations of unique BSTs by selecting each node within the range as a root and recursively constructing 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.
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.