ลบโหนดใบที่มีค่า k ใน Binary Tree ใน C++

บทนำ

ลบโหนดใบ (Leaf Node) ที่มีค่าเท่ากับ k ออกจาก Binary Tree โดยใช้ Recursive Post-order Traversal

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

1. Recursive ไปยังลูกซ้ายและขวาก่อน
2. อัปเดต left/right pointer ด้วยผลลัพธ์จาก recursive call
3. ถ้าโหนดปัจจุบันเป็นใบ (left=null, right=null) และ data == k → คืน NULL (ลบ)
4. มิฉะนั้น → คืน root (เก็บไว้)

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

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

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

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

Node* deleteLeafNodes(Node* root, int k) {
    if (root == NULL) {
        return nullptr;
    }
    root->left = deleteLeafNodes(root->left, k);
    root->right = deleteLeafNodes(root->right, k);
    if (root->data == k && root->left == NULL && root->right == NULL) {
        return nullptr;
    }
    return root;
}

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main(void) {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right->right = newNode(5);
    root->right->left = newNode(4);
    root->right->right->left = newNode(4);
    root->right->right->right = newNode(4);
    deleteLeafNodes(root, 4);
    cout << "Tree: ";
    inorder(root);
    cout << endl;
    return 0;
}

ผลลัพธ์

Tree: 3 2 1 3 5

คำอธิบาย

โหนดใบที่มีค่า 4 ทั้ง 4 ตัวถูกลบ โหนดในที่มีค่า 4 (right child of 3) ไม่ถูกลบเพราะไม่ใช่ใบ

สรุป

Post-order traversal เหมาะสำหรับการลบโหนด เพราะประมวลผลลูกก่อน แล้วค่อยตัดสินใจกับโหนดปัจจุบัน