Sponsored
Sponsored
This approach uses recursion to build all possible full binary trees for a given number of nodes. Since the problem exhibits overlapping subproblems, we can optimize the solution using memoization to store the results of previously solved subproblems. This significantly reduces the number of calculations needed.
The time complexity is O(2^N) due to the recursive generation of all possible subtrees. However, memoization helps to reduce the number of redundant calculations. The space complexity is also O(2^N) due to the storage of previously computed subtrees in the memo dictionary.
1class TreeNode {
2 constructor(val = 0, left = null, right = null) {
3 this.val = val;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9const memo = {};
10
11function allPossibleFBT(N) {
12 if (N % 2 === 0) return [];
13 if (N === 1) return [new TreeNode(0)];
14 if (memo[N]) return memo[N];
15
16 const result = [];
17 for (let left = 1; left < N; left += 2) {
18 for (let leftNode of allPossibleFBT(left)) {
19 for (let rightNode of allPossibleFBT(N - 1 - left)) {
20 const root = new TreeNode(0);
21 root.left = leftNode;
22 root.right = rightNode;
23 result.push(root);
24 }
25 }
26 }
27 memo[N] = result;
28 return result;
29}The JavaScript function allPossibleFBT implements a similar memoized recursive approach as the Python version. It creates instances of TreeNode for the roots of subtrees, and memoizes results to avoid redundant calculations for the same N. This helps in creating and efficiently storing valid trees.
This approach uses dynamic programming through an iterative method to build trees from the bottom up. We generate trees with increasingly larger numbers of nodes by combining smaller full binary trees, ensuring that each construction step builds on the last.
This method maintains a time complexity of O(2^N) and a space complexity of O(2^N) due to stored references of constructed trees. While iterative, it effectively mirrors the recursive/memoized strategies through explicit storage of previous calculations.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
vector<TreeNode*> allPossibleFBT(int N) {
vector<vector<TreeNode*>> dp(N + 1);
if (N % 2 == 0) return {};
dp[1] = {new TreeNode(0)};
for (int n = 3; n <= N; n += 2) {
vector<TreeNode*> result;
for (int left = 1; left < n; left += 2) {
for (auto* leftTree : dp[left]) {
for (auto* rightTree : dp[n - left - 1]) {
TreeNode* root = new TreeNode(0);
root->left = leftTree;
root->right = rightTree;
result.push_back(root);
}
}
}
dp[n] = result;
}
return dp[N];
}The C++ solution utilizes a dynamic programming array dp where each entry dp[i] holds all the full binary trees possible with i nodes. Starting from the simplest case with one node, we iteratively combine smaller trees to build larger trees while ensuring balanced distribution between left and right subtrees, thereby leveraging previously computed solutions to optimize for new tree constructions.