Unique Binary Search Trees II ใน C++

สมมติว่าเรามีจำนวนเต็ม n เราต้องสร้างต้นไม้ค้นหาไบนารีที่มีโครงสร้างแตกต่างกันทั้งหมดซึ่งเก็บค่าจาก 1 ถึง n ตัวอย่างเช่น หากอินพุตคือ 3 ต้นไม้จะมีดังนี้

ขั้นตอนการแก้ปัญหา

• กำหนดฟังก์ชันเวียนเกิดชื่อ generate() ซึ่งรับ low และ high
• กำหนดโหนดต้นไม้ชื่อ temp
• ถ้า low > high ให้แทรก null ลงใน temp และคืนค่า temp
• for i ในช่วง low ถึง high
  • left_subtree := generate(low, i - 1)
  • right_subtree := generate(i + 1, high)
  • current := i
  • for j ในช่วง 0 ถึงขนาดของ left_subtree
    • for k ในช่วง 0 ถึงขนาดของ right_subtree
      • curr_node := สร้างโหนดต้นไม้หนึ่งโหนดด้วยค่า current
      • ซ้ายของ curr_node := left_subtree[j]
      • ขวาของ curr_node := right_subtree[k]
      • แทรก curr_node ลงใน temp
• คืนค่า temp
• เริ่มต้นเรียกฟังก์ชัน generate() ด้วยค่า 1 และ n เพื่อสร้างต้นไม้ทั้งหมด

ตัวอย่าง (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 insert(TreeNode **root, int val){ 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()){ 
        TreeNode *temp = q.front(); 
        q.pop(); 
        if(!temp->left){ 
            if(val != NULL) 
                temp->left = new TreeNode(val); 
            else 
                temp->left = new TreeNode(0); 
            return; 
        } 
        else{ 
            q.push(temp->left); 
        } 
        if(!temp->right){ 
            if(val != NULL) 
                temp->right = new TreeNode(val); 
            else 
                temp->right = new TreeNode(0); 
            return; 
        } 
        else{ 
            q.push(temp->right); 
        } 
    } 
} 

TreeNode *make_tree(vector<int> v){ 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; i < v.size(); i++){ 
        insert(&root, v[i]); 
    } 
    return root; 
} 

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 == NULL || curr->val == 0){ 
                cout << "null" << ", "; 
            } 
            else{ 
                cout << curr->val << ", "; 
            } 
        } 
    } 
    cout << "]" << endl; 
} 

class Solution { 
public: 
    vector<TreeNode*> generate(int low, int high) { 
        vector<TreeNode*> temp; 
        if(low > high){ 
            temp.push_back(NULL); 
            return temp; 
        } 
        for(int i = low; i <= high; i++){ 
            vector<TreeNode*> leftSubtree = generate(low, i - 1); 
            vector<TreeNode*> rightSubtree = generate(i + 1, high); 
            int current = i; 
            for(int j = 0; j < leftSubtree.size(); j++){ 
                for(int k = 0; k < rightSubtree.size(); k++){ 
                    TreeNode* currentNode = new TreeNode(current); 
                    currentNode->left = leftSubtree[j]; 
                    currentNode->right = rightSubtree[k]; 
                    temp.push_back(currentNode); 
                } 
            } 
        } 
        return temp; 
    } 
    
    vector<TreeNode*> generateTrees(int n) { 
        if(!n){ 
            vector<TreeNode*> r; 
            return r; 
        } 
        return generate(1, n); 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<TreeNode*> v = ob.generateTrees(3); 
    for(int i = 0; i < v.size(); i++) 
        tree_level_trav(v[i]); 
}

อินพุต

3

เอาต์พุต

[1, 2, 3, ] [1, 3, 2, ] [2, 1, 3, ] [3, 1, 2, ] [3, 2, 1, ]