Given an integer n, return a list of all possible full binary trees with n nodes. Each node of each tree in the answer must have Node.val == 0.
Each element of the answer is the root node of one possible tree. You may return the final list of trees in any order.
A full binary tree is a binary tree where each node has exactly 0 or 2 children.
Example 1:
Input: n = 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]]
Example 2:
Input: n = 3 Output: [[0,0,0]]
Constraints:
1 <= n <= 20
给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。
答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。
真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。
示例 1：
输入：n = 7 输出：[[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]]
示例 2：
输入：n = 3 输出：[[0,0,0]]
提示：
1 <= n <= 20
| Language | Runtime | Memory | Submission Time |
|---|---|---|---|
| javascript | 224 ms | 27.8 MB | 2019/01/31 17:40 |
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number} N
* @return {TreeNode[]}
*/
var allPossibleFBT = function(N) {
if (N % 2 === 0) return [];
if (N === 1) return [new TreeNode(0)];
var trees = [];
for (var i = 1; i <= N - 2; i+=2) {
const left = allPossibleFBT(i);
const right = allPossibleFBT(N - 1 - i);
for (var j=0; j<left.length; j++) {
for (var k=0; k<right.length;k++) {
var current = new TreeNode(0);
current.left = left[j];
current.right = right[k];
trees.push(current);
}
}
}
return trees;
};递归思路。可以画一下图，递归n === 1, n === 3, n === 5 的情况方便理解。
递归出口为 n === 1 的时候。
new 一个节点，递归左右子树，得到左右子树所有可能的满二叉树。然后这些子树分别与这个根结点组合就行。一个双重循环搞定。