All Possible Full Binary Trees
A full binary tree is a binary tree where each node has exactly 0 or 2 children.
Return a list of all possible full binary trees with N nodes. Each element of the answer is the root node of one possible tree.
Each node of each tree in the answer must have node.val = 0.
You may return the final list of trees in any order.
Example 1:
Input: 7
Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
Explanation:
Note:
1 <= N <= 20
Solution
// recursive
const allPossibleFBT = function(N) {
if (N % 2 === 0) {
return [];
}
if (N === 1) {
return [new TreeNode(0)];
}
const output = [];
for (let i = 1; i <= N - 1; i += 2) {
const lefts = allPossibleFBT(i);
const rights = allPossibleFBT(N - 1 - i);
for (const left of lefts) {
for (const right of rights) {
const root = new TreeNode(0);
root.left = left;
root.right = right;
output.push(root);
}
}
}
return output;
};
// dp
const allPossibleFBT = function(N) {
const dp = [...new Array(N + 1)].map(() => []);
dp[1].push(new TreeNode(0));
for (let i = 2; i <= N; i++) {
for (let j = 0; j <= i - 1; j++) {
const lefts = dp[j].map(clone);
const rights = dp[i - j - 1].map(clone);
for (const left of lefts) {
for (const right of rights) {
const root = new TreeNode(0);
root.left = left;
root.right = right;
dp[i].push(root);
}
}
}
}
return dp[N];
};
function clone(root) {
if (!root) {
return null;
}
const cloned = new TreeNode(0);
cloned.left = clone(root.left);
cloned.right = clone(root.right);
return cloned;
}
comments powered by Disqus