【LeetCode 894】 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:

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

思路

递归。根节点的两个子树，即i个节点和N-1-i个节点的子问题的组合。
可以存储解，节省时间。

代码

递归：

/**
 * 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 {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        if (N % 2 == 0) return {};
        if (N == 1) return {new TreeNode(0)};
        vector<TreeNode*> ans;
        
        for (int i=1; i<N; ++i) {
            for (auto& l : allPossibleFBT(i)) {
                for (auto& r : allPossibleFBT(N-1-i)) {
                    TreeNode* root = new TreeNode(0);
                    root->left = l;
                    root->right = r;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
};

记忆化搜索

/**
 * 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 {
public:
    vector<TreeNode*> allPossibleFBT(int N) {
        return trees(N);
    }
    
    vector<TreeNode*>& trees(int N) {
        if (mp.count(N)) return mp[N];
        vector<TreeNode*>& ans = mp[N];
        
        if (N % 2 == 0) return ans = {};
        if (N == 1) return ans = {new TreeNode(0)};
        
        for (int i=0; i<N; ++i) {
            for (const auto& l : trees(i)) {
                for (const auto& r : trees(N-i-1)) {
                    TreeNode* root = new TreeNode(0);
                    root->left = l;
                    root->right = r;
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }
    
private:
    int maxN = 20+1;
    map<int, vector<TreeNode*>> mp;
};

和指针有关的就有点懵。