กู้คืน Binary Search Tree ใน C++

สมมติว่าเรามี Binary Search Tree (BST) หนึ่งต้น พิจารณาว่ามีองค์ประกอบสองตัวของ BST นี้ถูกสลับที่กัน เราต้องกู้คืน BST ให้กลับสู่สภาพเดิม

เช่น ต้นไม้ที่กำหนดเป็นแบบแรก (ต้นแรก) ต้นไม้ที่กู้คืนแล้วจะเป็นแบบที่สอง

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

• กำหนดตัวอ้างอิง prev, first, second สำหรับโหนด
• กำหนดเมธอด findProblem() ที่รับโหนด
• ถ้าโหนดเป็น null ให้คืนค่า
• เรียก findProblem(ซ้ายของโหนด)
• ถ้า prev ไม่เป็น null และค่าของ prev > ค่าของโหนด
  • ถ้า first เป็น null แล้ว first = prev
  • second := โหนด
• prev := โหนด
• เรียก findProblem(ขวาของโหนด)
• จากเมธอดหลัก ทำดังนี้
  • เริ่มต้น prev, first, second เป็น null เรียก findProblem(root) และสลับค่าของโหนด first และ second

ตัวอย่างโค้ด C++

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

class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        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:
    TreeNode* prev;
    TreeNode* first;
    TreeNode* second;
    void swapValue(TreeNode* first, TreeNode* second){
        int x = first->val;
        first->val = second -> val;
        second->val = x;
    }
    void findProblem(TreeNode* node){
        if(!node || node->val == 0)return;
        findProblem(node->left);
        if((prev!=NULL && prev->val != 0) && prev->val > node->val){
            if(!first){
                first = prev;
            }
            second = node;
        }
        prev = node;
        findProblem(node->right);
    }
    void recoverTree(TreeNode* root) {
        prev = first = second = NULL;
        findProblem(root);
        swapValue(first, second);
    }
};

int main(){
    vector<int> v = {1,3,NULL,NULL,2};
    TreeNode *root = make_tree(v);
    Solution ob;
    ob.recoverTree(root);
    tree_level_trav(root);
}

อินพุต

{1,3,NULL,NULL,2}

เอาต์พุต

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