All Possible Full Binary Trees

LeetCode

第18天。

今天的题目是 All Possible Full Binary Trees :

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:

1
2
3
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

这道题就是一个穷举的问题，我们知道完全二叉树的节点个数一定是奇数，所以可以先把N为偶数的输入先处理掉，然后就是怎么穷举的问题了。显然，一个完全二叉树的子树一定也是完全二叉树，所以我们可以以1,3,5...,N-2的方式穷举出出左子树中节点的个数i，已知左子树节点个数，那么右子树节点的个数就为N-i-1,我们先把左子树和右子树的可能都算出来，然后就再计算它们两两组合的所有可能即可得到所有节点个数为N的完全二叉树的情况。总的来说，就是一个大问题化简成小问题的思路。所以我们可以写出如下代码：

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
TreeNode *copyTree(TreeNode *root) {
    if (root == nullptr) return nullptr;
    TreeNode *res = new TreeNode(0);
    res->left = copyTree(root->left);
    res->right = copyTree(root->right);
    return res;
}

vector<TreeNode*> allPossibleFBT(int N) {
    vector<TreeNode*> res;   
    if (N % 2 == 0) return res;

    vector<vector<TreeNode*>> dp(N+1);
    dp[1].push_back(new TreeNode(0));

    for(int i = 1;i < dp.size();i+=2) {
        // dp[i];
        for(int j = 1;j < i;j+=2) {
            vector<TreeNode*> &left = dp[j];
            vector<TreeNode*> &right = dp[(i-j-1)];
            for(auto &l: left) {
                for(auto &r: right) {
                    TreeNode *node = new TreeNode(0);
                    node->left = copyTree(l);
                    node->right = copyTree(r);
                    dp[i].push_back(node);        
                }
            }
        }
    }
    return dp[N];
}

然后你会发现好像可以用一个数组来存在已经求解出来的结果，如果再一次求，我们可以直接返回了：

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
vector<TreeNode*> &allPossibleFBT(int N, vector<vector<TreeNode*>> &cache) {
    if (cache[N].size() != 0) return cache[N];

    for(int i = 1;i < N;i++) {
        vector<TreeNode*> &left = allPossibleFBT(i, cache);
        vector<TreeNode*> &right = allPossibleFBT(N - i - 1, cache);
        for(auto l: left) {
            for(auto r: right) {
                TreeNode *node = new TreeNode(0);
                node->left = l;
                node->right = r;
                cache[N].push_back(node);
            }
        }
    }
    return cache[N];
}

vector<TreeNode*> allPossibleFBT(int N) {
    vector<TreeNode*> res;   
    if (N % 2 == 0) return {};
    vector<vector<TreeNode*>> cache(21);

    cache[1].push_back(new TreeNode(0));
    return allPossibleFBT(N, cache);
}

如果熟悉动态规划的话，就会发现可以自顶向下的求解方式转成自底向上的求解方式，这里我们就不需要用递归去求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<TreeNode*> allPossibleFBT(int N) {
    vector<TreeNode*> res;   
    if (N % 2 == 0) return res;

    vector<vector<TreeNode*>> dp(N+1);
    dp[1].push_back(new TreeNode(0));

    for(int i = 1;i < dp.size();i+=2) {
        // dp[i];
        for(int j = 1;j < i;j+=2) {
            for(auto l: dp[j]) {
                for(auto r: dp[i-j-1]) {
                    TreeNode *node = new TreeNode(0);
                    node->left = copyTree(l);
                    node->right = copyTree(r);
                    dp[i].push_back(node);        
                }
            }
        }
    }
    return dp[N];
}

最后，这份代码在LeetCode大概只能超过50%，如果要进一步，只有把copyTree去掉，直接赋值。这种方式是可行的，但是感觉只是在刷题时的一种技巧而已：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<TreeNode*> allPossibleFBT(int N) {
    vector<TreeNode*> res;   
    if (N % 2 == 0) return res;

    vector<vector<TreeNode*>> dp(N+1);
    dp[1].push_back(new TreeNode(0));

    for(int i = 1;i < dp.size();i+=2) {
        // dp[i];
        for(int j = 1;j < i;j+=2) {
            for(auto l: dp[j]) {
                for(auto r: dp[i-j-1]) {
                    TreeNode *node = new TreeNode(0);
                    node->left = l;//copyTree(l);
                    node->right = r;//copyTree(r);
                    dp[i].push_back(node);        
                }
            }
        }
    }
    return dp[N];
}