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