leetcode_894. 所有可能的满二叉树（C++，详细讲解）_leetcode 894

题目

原题链接

满二叉树是一类二叉树，其中每个结点恰好有 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]]
1
2

提示：

• 1 <= N <= 20

思路

观察上图与题目，我们可以发现，一棵题目所示的“满二叉树”，是有奇数个节点的。

为什么呢？首先我们知道，一个节点只可能有 0 或 2 个子节点，所以，除了根节点之外的所以有其他节点，其实都是成对成对出现的，如果是偶数个节点，必然会出现有一个节点只有一个子节点，而这就不符合满二叉树的定义了。

对于每一个递归函数，都有一个参数 N，表示分配给这个函数建树用的节点总数。很显然，该函数内部需要递归向左右子树继续建树，如果分配给左子树 i 个节点，右子树就只剩下 N-i-1 个节点可供分配了。注意，要 -1，别忘了根节点。
（关于 i 的取值，一个 for 循环搞定，注意取值为奇数，也就是 i+=2 ，同时不能等于 N ，详见下面代码）

边界条件：

• N为偶数，返回空列表
• N为1，返回根节点

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    vector<TreeNode*> temp;
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        vector<TreeNode*> num;
        if(N % 2 == 0) return num;
        if(N == 1) {
            num.push_back(new TreeNode(0));
            return num;
        }

        for(int i = 1; i <= N-2; i += 2){
            vector<TreeNode*> left = allPossibleFBT(i);
            vector<TreeNode*> right = allPossibleFBT(N-1-i);
            for(int j = 0; j < left.size(); ++ j) {
                for(int k = 0; k < right.size(); ++ k) {
                    TreeNode *root = new TreeNode(0);
                    root -> left = left[j];
                    root -> right = right[k];
                    num.push_back(root);
                }
            }
        }
        return num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35