leetcode 题库894-- 所有可能的满二叉树_判断满二叉树leetcode

894-- 所有可能的满二叉树

思路：
这道题，要求满二叉树的所有可能，采用递归比较简单。
递归流程：
根节点占一个节点，然后就是考虑左右子树的可能。首先根据满二叉树的性质确定递归中断的条件：不能是偶数节点;节点数为1,就只有根节点。不需要在递归下去。
左右子树的可能通过递归求得，最后就是将左右子树和根节点组合。
优化：将前面各种节点的结果保存，后续不同重复递归计算。

	//这个题考虑递归
    //这个函数意思：返回n个节点构成符合条件的树列表
    vector<TreeNode*> allPossibleFBT(int N) {
        //条件判断
        //满二叉树必然节点数为奇数
        vector<TreeNode*> res;
        if(N & 1 == 0) 
        {
            //偶数返回空
            return res;
        }
        if(N == 1)
        {
            //只有一个点
            res.push_back(new TreeNode(0));
            return res;
        }

        //递归找左右子树
        //左子树的节点数为奇数, 1,3,5......N-2  ,根节点和右节点最少要2个节点
        for(int i = 1; i < N-1; i+=2)
        {
            vector<TreeNode*> left = allPossibleFBT(i);
            vector<TreeNode*> right = allPossibleFBT(N-1-i);

            //将左右子树进行组合
            for(int m = 0; m < left.size(); ++m)
            {
                for(int n = 0; n < right.size(); ++n)
                {
                    TreeNode*root = new TreeNode(0);
                    root->left = left[m];
                    root->right = right[n];

                    res.push_back(root);
                }
            }
        }
        
        return res;
    }
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
36
37
38
39
40
41