leetcode题解-894-所有可能的满二叉树

发表于 | 更新于

题目

My way

记忆化搜索

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
42
43
44
45
46
47
48
49
50
51
/**
 * 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 {
private:
unordered_map<int, vector<TreeNode*>> memo;

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

        //if (memo.count(N))    return memo[N];
        auto it = memo.find(N);
        if (it != memo.end())   return it->second;

        vector<TreeNode*> vt;

        if (N == 1)
        {
            vt.push_back(new TreeNode(0));
        } 
        else if (N % 2 == 1)
        {
            for (int x = 0; x < N; ++x)
            {
                int y = N - 1 - x;
                for (auto left: allPossibleFBT(x))
                {
                    for (auto right: allPossibleFBT(y))
                    {
                        TreeNode* bns = new TreeNode(0);
                        bns->left = left;
                        bns->right = right;
                        vt.push_back(bns);
                    }
                }
            }
        }
        memo.insert(make_pair(N, vt));
    
        return memo[N];
    }
};