C++ Subtree ใหญ่ที่สุดที่มีจำนวน 1 และ 0 เท่ากัน

ได้รับ Binary Tree มา ตอนนี้เราต้องหา Subtree ใหญ่ที่สุดที่มีจำนวน 1 และ 0 เท่ากัน ต้นไม้นี้มีแค่ 0 และ 1 เท่านั้น

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

ในวิธีนี้ เราจะแทนที่โหนดที่มีค่า 0 ด้วย -1 การทำเช่นนี้จะทำให้โปรแกรมง่ายขึ้น เพราะตอนนี้เราต้องการหา Subtree ใหญ่ที่สุดที่มีผลรวมเท่ากับ 0

ตัวอย่าง

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

#include <iostream> 
using namespace std; 

int maxi = -1; 

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

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

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

int calculatingmax(struct node* root){ 
    int a = 0, b = 0; 
    if (root == NULL) return 0; 
    a = calculatingmax(root->right); 
    a = a + 1; 
    b = calculatingmax(root->left); 
    a = b + a; 
    if (root->data == 0) 
        if (a >= maxi) maxi = a; 
    return a; 
} 

int calc_sum(struct node* root){ 
    if (root != NULL){ 
        if (root->data == 0) root->data = -1; 
    } 
    int a = 0, b = 0; 
    if (root->left != NULL) a = calc_sum(root->left); 
    if (root->right != NULL) b = calc_sum(root->right); 
    root->data += (a + b); 
    return root->data; 
} 

int main(){ 
    struct node* root = newnode(1); 
    root->right = newnode(0); 
    root->right->right = newnode(1); 
    root->right->right->right = newnode(1); 
    root->left = newnode(0); 
    root->left->left = newnode(1); 
    root->left->left->left = newnode(1); 
    root->left->right = newnode(0); 
    root->left->right->left = newnode(1); 
    root->left->right->left->left = newnode(1); 
    root->left->right->right = newnode(0); 
    root->left->right->right->left = newnode(0); 
    root->left->right->right->left->left = newnode(1); 
    calc_sum(root); 
    calculatingmax(root); 
    cout << maxi; 
    return 0; 
}

ผลลัพธ์

6

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

ในวิธีนี้ เราอัปเดตโหนดที่มีค่า 0 เป็น -1 แล้วปัญหาลดรูปเหลือการหา Subtree ใหญ่ที่สุดที่มีผลรวมเท่ากับ 0 ระหว่างการอัปเดตนี้ เรายังอัปเดตโหนดทุกตัวด้วยค่าผลรวมของ Subtree ที่รากอยู่ที่โหนดนั้น แล้วใช้ฟังก์ชันที่สองตรวจสอบทุกโหนดที่มีค่า 0 และหาจำนวนโหนดสูงสุดในต้นไม้นั้น

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาการหา Largest subtree having equal no of 1's and 0's เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์