题目
all-possible-full-binary-trees
题目描述
满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。
返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。
答案中每个树的每个结点都必须有 node.val=0。
你可以按任何顺序返回树的最终列表。
样例
输入：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]]
解释：
image.png
思路
递归左右子树的所有可能性
代码
public List<TreeNode> allPossibleFBT(int N) {
List<TreeNode> tree = new ArrayList<>();
if (N == 0)
return tree;
if (N == 1) {
tree.add(new TreeNode(0));
return tree;
}
for (int i = 1; i <= N - 1; i += 2) {
List<TreeNode> treeL = allPossibleFBT(i);
List<TreeNode> treeR = allPossibleFBT(N - i - 1);
for (TreeNode l : treeL) {
for (TreeNode r : treeR) {
TreeNode root = new TreeNode(0);
root.left = l;
root.right = r;
tree.add(root);
}
}
}
return tree;
}
结果
image.png
