ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือ ค้นหาโหนดที่ลึกที่สุดในไบนารีทรี .
Binary Tree เป็นโครงสร้างข้อมูลพิเศษที่ใช้เพื่อการจัดเก็บข้อมูล ต้นไม้ไบนารีมีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน
โหนดที่ลึกที่สุดในไบนารีทรี คือโหนดที่มีความสูงสูงสุดในต้นไม้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ข้อมูลเข้า :
เอาท์พุต :8
แนวทางการแก้ปัญหา
อาจมีหลายวิธีในการแก้ปัญหานี้ เนื่องจากคุณต้องค้นหาความสูงและข้ามต้นไม้ไปยังโหนดสุดท้ายที่ระดับความสูงแล้วส่งคืน การแก้ปัญหาทั้งหมดจะอยู่บนหลักการนี้เท่านั้น เราได้พูดคุยถึงวิธีแก้ปัญหาที่ได้ผลและเหมาะสมที่สุด
วิธีแก้ปัญหาอย่างง่ายคือการใช้การข้ามผ่านของต้นไม้และรักษาระดับไว้ หากระดับปัจจุบันมากกว่าระดับสูงสุด เราจะเริ่มต้นโหนดเป็นโหนดที่ลึกที่สุด หลังจากที่ข้ามโหนดทั้งหมดของทรีแล้ว เราจะส่งคืนโหนดที่ลึกที่สุด สำหรับการข้ามต้นไม้ เราจะใช้การเรียกซ้ำ
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <iostream>
using namespace std;
struct Node{
int data;
struct Node *left, *right;
};
Node *newNode(int data){
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findDeepestNodeRec(Node *root, int currentLevel, int &maxLevel, int &deepestNode){
if (root != NULL){
findDeepestNodeRec(root->left, ++currentLevel, maxLevel, deepestNode);
if (currentLevel > maxLevel){
deepestNode = root->data;
maxLevel = currentLevel;
}
findDeepestNodeRec(root->right, currentLevel, maxLevel, deepestNode);
}
}
int findDeepestNodeBT(Node *root){
int deepestNode = 0;
int maxLevel = 0;
findDeepestNodeRec(root, 0, maxLevel, deepestNode);
return deepestNode;
}
int main(){
Node* root = newNode(3);
root->left = newNode(5);
root->right = newNode(4);
root->left->left = newNode(1);
root->left->right = newNode(9);
root->right->left = newNode(6);
root->right->left->right = newNode(8);
cout<<"The deepest node of the given binary tree is "<<findDeepestNodeBT(root);
return 0;
} ผลลัพธ์
The deepest node of the given binary tree is 8
แนวทางอื่น การแก้ปัญหาคือการหาความสูงของต้นไม้ที่กำหนด แล้วคืนโหนดซึ่งอยู่ที่ระดับเท่ากับความสูงของต้นไม้
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data; struct Node *left, *right;
};
Node *newNode(int data){
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int calcHeight(Node* root){
if(!root) return 0;
int leftHt = calcHeight(root->left) + 1;
int rightHt = calcHeight(root->right) + 1;
return max(leftHt, rightHt);
}
void findDeepestNodeBT(Node* root, int levels){
if(!root) return;
if(levels == 1)
cout << root->data;
else if(levels > 1){
findDeepestNodeBT(root->left, levels - 1);
findDeepestNodeBT(root->right, levels - 1);
}
}
int main(){
Node* root = newNode(3);
root->left = newNode(5);
root->right = newNode(4);
root->left->left = newNode(1);
root->left->right = newNode(9);
root->right->left = newNode(6);
root->right->left->right = newNode(8);
int maxHeight = calcHeight(root);
cout<<"The deepest node of the binary tree is ";
findDeepestNodeBT(root, maxHeight);
return 0;
} ผลลัพธ์
The deepest node of the binary tree is 8
