C++의 이진 트리에서 가장 깊은 노드 찾기

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

이진 트리는 데이터 저장 목적으로 사용되는 특수 데이터 구조입니다. 바이너리 트리에는 각 노드가 최대 2개의 자식을 가질 수 있다는 특수한 조건이 있습니다.

이진 트리에서 가장 깊은 노드 트리에서 가능한 최대 높이에 있는 노드입니다.

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

입력:

출력 :8

솔루션 접근 방식

이 문제를 해결하는 방법은 여러 가지가 있을 수 있습니다. 높이를 찾아 트리를 가로질러 높이의 마지막 노드로 이동한 다음 반환해야 하기 때문입니다. 모든 솔루션은 이 원칙에만 있습니다. 여기에서 우리는 몇 가지 유망하고 최적화된 솔루션에 대해 논의했습니다.

문제에 대한 간단한 해결책은 현재 레벨이 maxLevel보다 큰 경우 트리의 inorder traversal을 사용하고 레벨 표시를 유지하는 것입니다. 노드를 deepestNode로 초기화합니다. 트리의 모든 노드를 탐색한 후 deepestNode를 반환합니다. 트리 순회를 위해 재귀를 사용합니다.

예시

솔루션 작동을 설명하는 프로그램

#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