C++에서 이진 트리의 최소 깊이 찾기

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 이진 트리의 최소 깊이를 찾는 것입니다.

Binary Tree는 각 노드가 최대 2개의 자식을 가질 수 있는 특별한 조건이 있습니다.

바이너리 트리의 최소 깊이는 루트 노드와 모든 리프 노드 사이의 최단 경로입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

출력

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