ความยาวเส้นทาง C++ มีจำนวนโค้งสูงสุด

เพื่อแก้ปัญหาที่เราได้รับไบนารีทรี ตอนนี้เราต้องหาเส้นทางที่มีจำนวนโค้งสูงสุด กล่าวคือ ทางโค้งจะพิจารณาเมื่อทิศทางของเส้นทางเปลี่ยนจากซ้ายไปขวาหรือกลับกัน เป็นต้น

อินพุต -

เอาท์พุต -

6

ในแนวทางนี้ เราจะสำรวจต้นไม้และติดตามการเคลื่อนไหวก่อนหน้า หากทิศทางเปลี่ยนไป เราก็แค่อัปเดตจำนวนโค้ง แล้วหาค่าสูงสุด

แนวทางในการหาแนวทางแก้ไข

ในแนวทางนี้ เราจะสำรวจเส้นทางทั้งหมด และพบจำนวนโค้งสูงสุดที่เราอัปเดตคำตอบของเรา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
struct Node { // structure of our node
    int key;
    struct Node* left;
    struct Node* right;
};
struct Node* newNode(int key){ // initializing our node
    struct Node* node = new Node();
    node->left = NULL;
    node->right = NULL;
    node->key = key;
    return node;
}
void maximumBends(struct Node* node,char direction, int bends,
                    int* maxBends, int soFar,int* len){
    if (node == NULL) // if null is reached
       return;
    if (node->left == NULL && node->right == NULL) { // if we reach the leaf node then
                                                   //we check if we have to update our answer or not
        if (bends > *maxBends) {
            *maxBends = bends;
            *len = soFar;
        }
    }
    else {
        if (direction == 'l') { // current direction is left
            maximumBends(node->left, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->right, 'r',bends + 1, maxBends,soFar + 1, len); // if we change direction so bend also increases
        }
        else {
            maximumBends(node->right, direction,bends, maxBends,soFar + 1, len);
            maximumBends(node->left, 'l',bends + 1, maxBends,soFar + 1, len); // same as when direction was left
        }
    }
}
int main(){
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(5);
    root->right->left = newNode(2);
    root->right->left->right = newNode(1);
    root->right->left->right->left = newNode(9);
    int len = 0, bends = 0, maxBends = -1;
    if(!root) // if tree is empty
       cout << "0\n";
    else{
        if (root->left) // if left subtree exists
            maximumBends(root->left, 'l',bends, &maxBends, 1, &len);
        if (root->right) // if right subtree exists
            maximumBends(root->right, 'r', bends,&maxBends, 1, &len);
        cout << len << "\n";
    }
    return 0;
}

ผลลัพธ์

4

คำอธิบายของโค้ดด้านบน

ในแนวทางข้างต้น เรากำลังสำรวจเส้นทางทั้งหมดและนับส่วนโค้งที่พบจนถึงตอนนี้เมื่อเราไปถึงจุดสิ้นสุดของเส้นทาง .i.e leaf node เราจะตรวจสอบว่าส่วนโค้งจนถึงที่นี่มากกว่าค่าสูงสุดก่อนหน้านี้หรือไม่ หาก เงื่อนไขเป็นจริง ดังนั้นเราจึงอัปเดตส่วนโค้งสูงสุดและความยาวของเส้นทางไปยังความยาวใหม่นี้ และนั่นคือวิธีที่โปรแกรมของเราดำเนินการ

บทสรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาเพื่อค้นหาความยาวของเส้นทางที่มีจำนวนโค้งสูงสุด นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์