题目
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
题目地址
讲解
这道题太适合用来训练递归了。与以前做过的题不同，这里的返回值是一个list。而且还需要对树比较了解。最好是先画出N=1到5的时候，树的结构，然后会发现一些规律。注意下i+=2，步长是2。
Java代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<TreeNode> allPossibleFBT(int N) {
List<TreeNode> result = new ArrayList<>();
if(N%2==0){
return result;
}
if(N==1){
result.add(new TreeNode(0));
return result;
}
for(int i=1;i<N;i+=2){
for(TreeNode l:allPossibleFBT(i)){
for(TreeNode r:allPossibleFBT(N-1-i)){
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
result.add(root);
}
}
}
return result;
}
}