C++ ความยาวเส้นทางที่มีจำนวนการบิด (Bends) มากที่สุด

เพื่อแก้ปัญหาที่เราได้รับต้นไม้ไบนารี (Binary Tree) ตอนนี้เราต้องหาเส้นทางที่มีจำนวนการบิด (Bends) มากที่สุด โดยการบิด (Bend) ถือว่าเกิดขึ้นเมื่อทิศทางของเส้นทางเปลี่ยนจากซ้ายไปขวาหรือขวาไปซ้าย เช่น

Input -

Output -

6

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

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

ในวิธีนี้ เราจะเดินผ่านทุกเส้นทาง และหาจำนวนการบิดสูงสุด แล้วอัปเดตคำตอบ

ตัวอย่าง

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

struct Node { 
    int key; 
    struct Node* left; 
    struct Node* right; 
}; 

struct Node* newNode(int key){ 
    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) return; 
    if (node->left == NULL && node->right == NULL) { 
        if (bends > *maxBends) { 
            *maxBends = bends; 
            *len = soFar; 
        } 
    } else { 
        if (direction == 'l') { 
            maximumBends(node->left, direction, bends, maxBends, soFar + 1, len); 
            maximumBends(node->right, 'r', bends + 1, maxBends, soFar + 1, len); 
        } else { 
            maximumBends(node->right, direction, bends, maxBends, soFar + 1, len); 
            maximumBends(node->left, 'l', bends + 1, maxBends, soFar + 1, len); 
        } 
    } 
} 

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) cout << "0\n"; 
    else{ 
        if (root->left) maximumBends(root->left, 'l', bends, &maxBends, 1, &len); 
        if (root->right) maximumBends(root->right, 'r', bends, &maxBends, 1, &len); 
        cout << len << "\n"; 
    } 
    return 0; 
}

ผลลัพธ์

4

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

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

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาการหา Path length having maximum number of bends เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์