C++ Hoán vị cặp nút lá trong cây nhị phân

Cho cây nhị phân, hoán vị từng cặp nút lá liền kề (theo thứ tự duyệt). Ví dụ:

→

Phương pháp giải

Duyệt cây, theo dõi 2 con trỏ firstLeaf, secondLeaf và bộ đếm count. Khi gặp nút lá: gán secondLeaf, tăng count. Nếu count chẵn → hoán đổi firstLeaf và secondLeaf. Nếu lẻ → firstLeaf = secondLeaf.

Ví dụ minh họa

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

struct Node {
    int data;
    Node *left, *right;
};

void Swap(Node** a, Node** b) {
    Node* temp = *a; *a = *b; *b = temp;
}

Node **firstLeaf, **secondLeaf;

void SwapLeafNodes(Node** root, int &count) {
    if (!*root) return;
    if (!(*root)->left && !(*root)->right) {
        secondLeaf = root;
        count++;
        if (count % 2 == 0) Swap(firstLeaf, secondLeaf);
        else firstLeaf = secondLeaf;
    }
    if ((*root)->left) SwapLeafNodes(&(*root)->left, count);
    if ((*root)->right) SwapLeafNodes(&(*root)->right, count);
}

Node* newNode(int data) {
    Node* t = new Node();
    t->data = data; t->left = t->right = NULL;
    return t;
}

void printInorder(Node* node) {
    if (!node) return;
    printInorder(node->left);
    cout << node->data << " ";
    printInorder(node->right);
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2); root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5); root->right->right = newNode(8);
    root->right->left->left = newNode(6); root->right->left->right = newNode(7);
    root->right->right->left = newNode(9); root->right->right->right = newNode(10);

    cout << "Inorder trước: "; printInorder(root); cout << "\n";
    int count = 0;
    SwapLeafNodes(&root, count);
    cout << "Inorder sau: "; printInorder(root); cout << "\n";
    return 0;
}

Kết quả

Inorder trước: 4 2 1 6 5 7 3 9 8 10
Inorder sau: 6 2 1 4 5 9 3 7 8 10

Giải thích

Duyệt cây, dùng 2 con trỏ và bộ đếm để hoán vị cặp lá liên tiếp. Count lẻ: lưu lá đầu. Count chẵn: hoán đổi 2 lá.

Kết luận

Đã giải bài toán hoán vị cặp nút lá bằng duyệt cây và 2 con trỏ. Code C++ chuyển được sang Java, Python, C. Hy vọng hữu ích.