Khôi phục cây tìm kiếm nhị phân trong C++

Cho một cây tìm kiếm nhị phân (BST), trong đó hai nút đã bị hoán đổi vị trí. Nhiệm vụ là khôi phục lại BST ban đầu.

Ví dụ: Nếu cây ban đầu như hình thứ nhất, cây sau khi khôi phục sẽ như hình thứ hai.

Giải thuật

Để giải bài toán này, ta thực hiện các bước sau:

• Định nghĩa các con trỏ prev, first, second tham chiếu đến các nút.
• Định nghĩa phương thức findProblem() nhận vào một nút.
• Nếu nút là null, trả về.
• Gọi đệ quy findProblem(cái con trái của nút).
• Nếu prev không null và giá trị prev > giá trị nút hiện tại:
  • Nếu first là null, gán first = prev.
  • Gán second = nút hiện tại.
• Cập nhật prev = nút hiện tại.
• Gọi đệ quy findProblem(cái con phải của nút).
• Từ phương thức chính:
  • Khởi tạo prev, first, second = null.
  • Gọi findProblem(root).
  • Hoán đổi giá trị của first và second.

Ví dụ minh họa (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);
    return 0;
}

Đầu vào

{1, 3, NULL, NULL, 2}

Đầu ra

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