ต้นไม้แบบทวิภาคเต็มรูปแบบทั้งหมดใน C++

ต้นไม้แบบทวิภาคเต็มรูป (Full Binary Tree) คือต้นไม้ที่ทุกโหนดมีลูก 0 หรือ 2 ตัว เท่านั้น ให้หาต้นไม้แบบทวิภาคเต็มรูปทั้งหมดที่มีโหนด N ตัว ค่าของทุกโหนดต้องเป็น 0 ลำดับของต้นไม้ในคำตอบไม่สำคัญ

ตัวอย่าง: N = 7 ได้ต้นไม้ 5 รูปแบบ

ขั้นตอนการแก้ปัญหา (Recursive + Memoization)

• แผนที่ m เก็บผลลัพธ์สำหรับแต่ละ N
• ฟังก์ชัน allPossibleFBT(N):
  • ถ้า N == 1 คืนต้นไม้โหนดเดียวค่า 0
  • ถ้า m มี N คืน m[N]
  • ans := [], required := N - 1 (โหนดสำหรับลูกซ้าย+ขวา)
  • วน left จาก 1 ถึง required-1 (ข้าม 2 เพราะไม่เป็น full binary tree):
    • right := required - left
    • leftPart := allPossibleFBT(left), rightPart := allPossibleFBT(right)
    • รวมทุกคู่จาก leftPart และ rightPart สร้างรากใหม่ค่า 0
  • เก็บ m[N] := ans คืน ans

ตัวอย่างโค้ด (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 == NULL) return;
    cout << "[";
    queue<TreeNode *> q;
    TreeNode *curr;
    q.push(root);
    q.push(NULL);
    while (q.size() > 1) {
        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 || curr == NULL) {
                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++) {
            int right = required - left;
            if(left == 2 || right == 2) continue;
            vector <TreeNode*> leftPart = allPossibleFBT(left);
            vector <TreeNode*> rightPart = allPossibleFBT(right);
            for(int j = 0; j < leftPart.size(); j++) {
                for(int k = 0; k < rightPart.size(); k++) {
                    TreeNode* root = new TreeNode(0);
                    root->left = leftPart[j];
                    root->right = rightPart[k];
                    ans.push_back(root);
                }
            }
        }
        return m[N] = ans;
    }
};

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

อินพุต

7

เอาต์พุต

[1, 1, 1, null, null, 1, 1, null, null, 1, 1, null, null, null, null, ] [1, 1, 1, null, null, 1, 1, 1, 1, null, null, null, null, null, null, ] [1, 1, 1, 1, 1, 1, 1, null, null, null, null, null, null, null, null, ] [1, 1, 1, 1, 1, null, null, null, null, 1, 1, null, null, null, null, ] [1, 1, 1, 1, 1, null, null, 1, 1, null, null, null, null, null, null, ]