ในปัญหานี้ เราได้รับไบนารีทรีและจำนวนเต็ม N ภารกิจคือการค้นหาโหนดที่ n ในการข้ามผ่านแบบไม่เรียงลำดับของทรีไบนารี
ต้นไม้ไบนารีมีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน
การข้ามผ่านเป็นกระบวนการในการเยี่ยมชมโหนดทั้งหมดของต้นไม้และอาจพิมพ์ค่าของพวกมันด้วย
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 6
ผลลัพธ์
3
คำอธิบาย
inorder traversal of tree : 4, 2, 5, 1, 6, 3, 7
แนวทางการแก้ปัญหา
แนวคิดคือการใช้การข้ามผ่านในลำดับของต้นไม้ไบนารีซึ่งทำได้โดยใช้การเรียกซ้ำ ในการโทรแต่ละครั้ง เราจะเรียก preOrder() สำหรับทรีย่อยทางซ้ายก่อน แล้วจึงข้ามโหนดรูท จากนั้นเรียก preOrder() ในระหว่างการข้ามผ่านนี้ เราจะนับจำนวนโหนดและพิมพ์โหนดที่นับเป็น N
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* createNode(int item){
Node* temp = new Node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void findInOrderTraversalRec(struct Node* node, int N){
static int count = 0;
if (node == NULL)
return;
if (count <= N) {
findInOrderTraversalRec(node->left, N);
count++;
if (count == N)
cout<<node->data;
findInOrderTraversalRec(node->right, N);
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
int N = 6;
cout<<N<<"th node in inorder traversal is ";
findInOrderTraversalRec(root, N);
return 0;
} ผลลัพธ์
6th node in inorder traversal is 3
