C++のバイナリツリーのすべての正しいノードの中から最大値を見つけます

この問題では、二分木が与えられます。私たちのタスクは、バイナリツリー内のすべての適切なノードの中から最大値を見つけることです。

問題の説明： ここでは、二分木のすべての正しい子ノードの中から最大値を見つける必要があります。

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

入力：

出力： 9

説明：

すべての正しいノードは次のとおりです：{2、8、9}。それらの最大数は9です。

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

この問題を解決するには、ツリーをトラバースして、適切な子が存在するかどうかを確認する必要があります。存在する場合は、maxRight要素と比較し、大きい場合は置き換えます。

ソリューションの動作を説明するプログラム

例

#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;
}

int findMaxRightNode(Node* root) {
   
   int maxRight = -100;

   if (root == NULL)
      return -1;

   if (root->right != NULL)
      maxRight = root->right->data;

   return max( findMaxRightNode(root->right), max(maxRight, findMaxRightNode(root->left) ) );
}

int main() {

   Node* root = newNode(5);
   root->left = newNode(3);
   root->right = newNode(2);
   root->left->left = newNode(1);
   root->left->right = newNode(8);
   root->right->left = newNode(6);
   root->right->right = newNode(9);

   cout<<"The maximum among all right nodes in Binary Tree is "<< findMaxRightNode(root);

   return 0;
}

出力

The maximum among all right nodes in Binary Tree is 9