C++ ลบโหนดบนเส้นทาง Root-to-Leaf ที่มีความยาว

กำหนดต้นไม้ (Tree) และเราต้องลบโหนดใบ (leaf node) ของเส้นทางที่มีความยาวน้อยกว่า k ที่กำหนด ตัวอย่างเช่น:

Input -

K = 4.

C++ ลบโหนดบนเส้นทาง Root-to-Leaf ที่มีความยาว K

Output -

C++ ลบโหนดบนเส้นทาง Root-to-Leaf ที่มีความยาว K

คำอธิบาย

เส้นทางคือ:
1. A -> B -> C -> E ความยาว = 4
2. A -> B -> C -> F ความยาว = 4
3. A -> B -> D ความยาว = 3
4. A -> G -> H ความยาว = 3
5. A -> B -> I ความยาว = 3

ตอนนี้คุณเห็นได้ว่าเส้นทาง 3, 4, 5 มีความยาว 3 ซึ่งน้อยกว่า k ที่กำหนด ดังนั้นเราลบโหนดใบของเส้นทางเหล่านี้ คือ D, H, I
ตอนนี้สำหรับเส้นทาง 4 และ 5 เมื่อ H และ I ถูกลบ เราสังเกตเห็นว่า G ตอนนี้ก็เป็นโหนดใบที่มีความยาวเส้นทาง 2 ดังนั้นเราลบโหนด G อีกครั้ง และโปรแกรมของเราจบที่นี่

เราจะเดินทางผ่านต้นไม้ในรูปแบบ post-order จากนั้นสร้างฟังก์ชันเรียกซ้ำที่ลบโหนดใบถ้าความยาวเส้นทางน้อยกว่า K

วิธีการหาคำตอบ

ในวิธีนี้ เราเดินทางใน post-order traversal ตอนนี้ เราลองเรียกซ้ำเพื่อลบโหนดใบที่มีความยาวเส้นทางน้อยกว่า k และทำต่อไปเช่นนี้

ตัวอย่าง

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

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

struct Node{
    // โครงสร้างของโหนดของเรา
    char data;
    Node *left, *right;
};

Node *newNode(int data){ // แทรกโหนดใหม่
    Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

Node *trimmer(Node *root, int len, int k){
    if (!root) // ถ้า root == NULL คืนค่า
        return NULL;
    root->left = trimmer(root->left, len + 1, k); // เดินทางผ่าน left subtree
    root->right = trimmer(root->right, len + 1, k); // เดินทางผ่าน right subtree
    if (!root->left && !root->right && len < k){
        delete root;
        return NULL;
    }
    return root;
}

Node *trim(Node *root, int k){
    return trimmer(root, 1, k);
}

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

int main(){
    int k = 4;
    Node *root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('G');
    root->left->left = newNode('C');
    root->left->right = newNode('D');
    root->left->left->left = newNode('E');
    root->left->left->right = newNode('F');
    root->right->left = newNode('H');
    root->right->right = newNode('I');
    printInorder(root);
    cout << "\n";
    root = trim(root, k);
    printInorder(root);
    return 0;
}

ผลลัพธ์

E C F B D A H G I
E C F B A

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

ในโค้ดนี้ เราใช้ฟังก์ชันเรียกซ้ำที่เดินทางผ่านต้นไม้ของเราและเก็บสถิติของ left และ right subtrees ตอนนี้เมื่อเราถึงโหนดใบ เราตรวจสอบความยาวเส้นทางจนถึงโหนดนั้น ถ้าความยาวเส้นทางน้อยกว่า เราลบโหนดนี้ และคืนค่า NULL มิฉะนั้น โค้ดจะดำเนินการต่อ

สรุป