ค้นหาความลึกขั้นต่ำของต้นไม้ไบนารีใน C++

ในปัญหานี้ เราได้รับไบนารีทรี งานของเราคือค้นหาความลึกขั้นต่ำของต้นไม้ไบนารี

Binary Tree มีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน

ความลึกขั้นต่ำของไบนารีทรีคือเส้นทางที่สั้นที่สุดระหว่างโหนดรูทไปยังโหนดปลายสุดใดๆ

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

ผลลัพธ์

2

แนวทางการแก้ปัญหา

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

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* left, *right;
};
int findMinDepthBT(Node *currentNode) {
   if (currentNode == NULL)
      return 0;
   if (currentNode->left == NULL && currentNode->right == NULL)
      return 1;
   if (!currentNode->left)
      return findMinDepthBT(currentNode->right) + 1;
   if (!currentNode->right)
      return findMinDepthBT(currentNode->left) + 1;
      return min(findMinDepthBT(currentNode->left),
   findMinDepthBT(currentNode->right)) + 1;
}
Node *newNode(int data) {
   Node *temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return (temp);
}
int main() {
   Node *root = newNode(5);
   root->left = newNode(2);
   root->right = newNode(9);
   root->left->left = newNode(5);
   root->left->right = newNode(1);
   root->left->left->left = newNode(7);
   root->left->left->right = newNode(3);
   cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
   return 0;
}

ผลลัพธ์

The minimum depth of binary tree is 2

วิธีนี้ค่อนข้างมีประสิทธิภาพ แต่เราสามารถใช้เทคนิคการข้ามผ่านอื่นๆ เพื่อค้นหาความลึกขั้นต่ำได้อย่างมีประสิทธิภาพมากขึ้น

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

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
struct lOrderQueue {
   Node *node;
   int depth;
};
int findMinDepthBT(Node *root) {
   if (root == NULL)
      return 0;
   queue<lOrderQueue> levelOrder;
   lOrderQueue deQueue = {root, 1};
   levelOrder.push(deQueue);
   while (levelOrder.empty() == false) {
      deQueue = levelOrder.front();
      levelOrder.pop();
      Node *node = deQueue.node;
      int depth = deQueue.depth;
      if (node->left == NULL && node->right == NULL)
         return depth;
      if (node->left != NULL) {
         deQueue.node = node->left;
         deQueue.depth = depth + 1;
         levelOrder.push(deQueue);
      }
      if (node->right != NULL) {
         deQueue.node = node->right;
         deQueue.depth = depth+1;
         levelOrder.push(deQueue);
      }
   }
   return 0;
}
Node* newNode(int data) {
   Node *temp = new Node;
   temp->data = data;
   temp->left = temp->right = NULL;
   return temp;
}
int main() {
   Node *root = newNode(5);
   root->left = newNode(2);
   root->right = newNode(9);
   root->left->left = newNode(5);
   root->left->right = newNode(1);
   root->left->left->left = newNode(7);
   root->left->left->right = newNode(3);
   cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
   return 0;
}

ผลลัพธ์

The minimum depth of binary tree is 2