Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from1ton. Return the answer in any order.
Example 1:
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1
Output: [[1]]
Constraints:
1 <= n <= 8
Intuition
Building all the left subtrees in that range and attaching
Let say 1 3 , It will have all trees possilble from 1 to 3
This will be attach all the trees between 1 & 3 to left
and so on
We can use DP to memoize but no need as constraints are low
Links
Video Links
Approach 1:
Recursion
C++
class Solution {
public:
vector<TreeNode*> buildTree(int start, int end) {
vector<TreeNode*> ans;
if(start > end) {
ans.push_back(NULL);
return ans;
}
for(int i = start; i <= end; ++i) {
vector<TreeNode*> leftSubTree = buildTree(start, i - 1);
vector<TreeNode*> rightSubTree = buildTree(i + 1, end);
/*
Building all the left subtrees in that range and attaching
Let say 1 3 , It will have all trees possilble from 1 to 3
This will be attach all the trees between 1 & 3 to left
and so on
*/
for(int j = 0; j < leftSubTree.size(); j++) {
for(int k = 0; k < rightSubTree.size(); k++) {
TreeNode* root = new TreeNode(i);
root->left = leftSubTree[j];
root->right = rightSubTree[k];
ans.push_back(root);
}
}
}
return ans;
}
vector<TreeNode*> generateTrees(int n) {
return buildTree(1, n);
}
};
