Đảo ngược đường đi trong BST bằng Queue (C++)

Cho cây tìm kiếm nhị phân (BST) và một khóa key. Đảo ngược thứ tự các nút trên đường đi từ gốc đến nút có giá trị key. Ví dụ minh họa qua hình ảnh (trước/sau khi đảo).

Cách tiếp cận

Dùng queue lưu các nút trên đường đi. Duyệt đệ quy tìm key: đẩy nút hiện tại vào queue. Khi tìm thấy key, gán giá trị nút hiện tại = đầu queue, pop queue. Quay lại (backtrack), tiếp tục gán giá trị từ queue cho các nút trên đường đi → đường đi bị đảo ngược.

Ví dụ

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

struct node {
    int key;
    struct node *left, *right;
};

struct node* newNode(int item) {
    struct node* temp = new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(struct node* root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}

void Reversing(struct node** node, int& key, queue<int>& q1) {
    if (node == NULL) return;
    if ((*node)->key == key) {
        q1.push((*node)->key);
        (*node)->key = q1.front();
        q1.pop();
    } else if (key < (*node)->key) {
        q1.push((*node)->key);
        Reversing(&(*node)->left, key, q1);
        (*node)->key = q1.front();
        q1.pop();
    } else if (key > (*node)->key) {
        q1.push((*node)->key);
        Reversing(&(*node)->right, key, q1);
        (*node)->key = q1.front();
        q1.pop();
    }
}

struct node* insert_node(struct node* node, int key) {
    if (node == NULL) return newNode(key);
    if (key < node->key) node->left = insert_node(node->left, key);
    else if (key > node->key) node->right = insert_node(node->right, key);
    return node;
}

int main() {
    struct node* root = NULL;
    queue<int> q1;
    int k = 80;
    root = insert_node(root, 50);
    insert_node(root, 30);
    insert_node(root, 20);
    insert_node(root, 40);
    insert_node(root, 70);
    insert_node(root, 60);
    insert_node(root, 80);
    cout << "Before Reversing :\n";
    inorder(root);
    cout << "\n";
    Reversing(&root, k, q1);
    cout << "After Reversing :\n";
    inorder(root);
    return 0;
}

Kết quả

Before Reversing : 20 30 40 50 60 70 80 After Reversing : 20 30 40 80 60 70 50

Giải thích

Đệ quy tìm key, đẩy các nút trên đường đi vào queue. Khi tìm thấy, gán giá trị từ đầu queue (phần tử cuối đường đi) cho nút hiện tại, pop queue. Khi backtrack, tiếp tục gán → đường đi đảo ngược.

Kết luận

Đã giải quyết đảo ngược đường đi trong BST dùng queue + đệ quy. Code C++ mẫu.