C++のバイナリツリーで最も深いノードを見つける

この問題では、二分木が与えられます。私たちのタスクは、バイナリツリーで最も深いノードを見つけることです。 。

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。二分木には、各ノードが最大2つの子を持つことができるという特別な条件があります。

二分木で最も深いノード ツリー内で可能な最大の高さにあるノードです。

問題を理解するために例を見てみましょう

入力：

出力：8

ソリューションアプローチ

高さを見つけて、高さの最後のノードまでツリーをトラバースして返す必要があるため、この問題を解決するには複数の方法があります。すべての解決策は、この原則のみに基づいています。ここでは、いくつかの有望で最適化されたソリューションについて説明しました。

この問題の簡単な解決策は、ツリーの順序どおりの走査を使用し、現在のレベルがmaxLevelより大きい場合にレベルマークを維持することです。ノードを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