Tất cả cây nhị phân đầy đủ có thể trong C++

Cây nhị phân đầy đủ (full binary tree): mỗi nút có 0 hoặc 2 con. Tìm tất cả cây đầy đủ có N nút, mỗi nút giá trị 0.

Ví dụ N=7 cho 5 cây khác nhau.

Giải thuật (Đệ quy + Memoization)

1. Map m lưu danh sách cây cho mỗi N.
2. allPossibleFBT(N):
3. Nếu N==1: trả về cây đơn nút.
4. Nếu có trong m, trả về.
5. required = N-1 (số nút cho 2 cây con).
6. Duyệt left từ 1 đến required-1 (bước 2 vì cây đầy đủ có số nút lẻ):
7. right = required - left.
8. Đệ quy lấy danh sách cây trái/phải, kết hợp mọi cặp tạo cây mới.
9. Lưu vào m[N] và trả về.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val; TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

void tree_level_trav(TreeNode* root) {
    if(!root) return;
    cout << "[";
    queue<TreeNode*> q; q.push(root); q.push(NULL);
    while(q.size() > 1) {
        TreeNode* curr = q.front(); q.pop();
        if(curr == NULL) q.push(NULL);
        else {
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
            if(curr->val == 0) cout << "null, ";
            else cout << curr->val << ", ";
        }
    }
    cout << "]" << endl;
}

class Solution {
public:
    map<int, vector<TreeNode*>> m;
    vector<TreeNode*> allPossibleFBT(int N) {
        if(N == 1) {
            vector<TreeNode*> temp;
            TreeNode* n = new TreeNode(0);
            temp.push_back(n);
            return temp;
        }
        if(m.count(N)) return m[N];
        vector<TreeNode*> ans;
        int required = N - 1;
        for(int left = 1; left < required; left += 2) {
            int right = required - left;
            vector<TreeNode*> leftPart = allPossibleFBT(left);
            vector<TreeNode*> rightPart = allPossibleFBT(right);
            for(auto l : leftPart)
                for(auto r : rightPart) {
                    TreeNode* root = new TreeNode(0);
                    root->left = l; root->right = r;
                    ans.push_back(root);
                }
        }
        return m[N] = ans;
    }
};

int main() {
    Solution ob;
    vector<TreeNode*> v = ob.allPossibleFBT(7);
    for(TreeNode* t : v) tree_level_trav(t);
    return 0;
}

Đầu vào

7

Đầu ra

5 cây đầy đủ khác nhau (xem output chi tiết trong code)