C++ สลับโหนดใบ (Leaf Nodes) แบบคู่ๆ ใน Binary Tree

ได้รับ Binary Tree มา งานคือการสลับโหนดใบ (Leaf Nodes) แบบคู่ๆ เช่น

Input -

Output -

ในปัญหานี้ เราจะติดตาม Pointer สองตัวที่ชี้ไปที่โหนดใบที่อยู่ติดกัน และสลับค่าของพวกเขา

วิธีการแก้ปัญหา

ในวิธีนี้ เราเดินผ่านต้นไม้ หาโหนดใบ และติดตามตัวนับ (Counter) เพื่อตรวจสอบจำนวนปัจจุบัน เทคนิคหลักคือ ถ้าตัวนับเป็นคี่ Pointer ตัวแรกจะชี้ไปที่โหนดนั้น ตอนที่ตัวนับเป็นคู่ เราสลับข้อมูล และโหนดใบก็ถูกสลับกัน

ตัวอย่าง

โค้ด C++ สำหรับวิธีการข้างต้น

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

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

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

Node **firstleaf; 
Node **secondleaf; 

void SwapTheLeafNodes(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) SwapTheLeafNodes(&(*root)->left, count); 
    if ((*root)->right) SwapTheLeafNodes(&(*root)->right, count); 
} 

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

void printInorder(Node* node){ 
    if (node == NULL) return; 
    printInorder(node->left); 
    printf("%d ", 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 traversal before swap:\n"; 
    printInorder(root); 
    cout << "\n"; 
    int count = 0; 
    SwapTheLeafNodes(&root, count); 
    cout << "Inorder traversal after swap:\n"; 
    printInorder(root); 
    cout << "\n"; 
    return 0; 
}

ผลลัพธ์

Inorder traversal before swap: 4 2 1 6 5 7 3 9 8 10
Inorder traversal after swap: 6 2 1 4 5 9 3 7 8 10

คำอธิบายโค้ด

ในวิธีนี้ เราสร้าง Pointer สองตัวติดตามโหนดใบ เราเดินผ่านต้นไม้ ตอนเจอโหนดใบ เราทำให้ Pointer ตัวที่สองชี้ไปที่โหนดนั้น แล้วเพิ่มตัวนับ ถ้าตัวนับเป็นคู่ สลับโหนด ถ้าเป็นคี่ แสดงว่ายังได้แค่ตัวแรกของคู่ จึงเก็บค่าไว้ใน Pointer ตัวแรก และฟังก์ชันก็ทำงานต่อไป

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหา Pairwise Swap leaf nodes in a binary tree เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา (ทั่วไปและมีประสิทธิภาพ) ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์