Tìm tối đa trong số tất cả các nút bên phải trong Cây nhị phân trong C ++

Trong bài toán này, chúng ta được đưa ra một Cây nhị phân. Nhiệm vụ của chúng tôi là tìm tối đa trong số tất cả các nút bên phải trong Cây nhị phân.

Mô tả sự cố: Ở đây, chúng ta cần tìm giá trị lớn nhất trong số tất cả các nút con bên phải của Cây nhị phân.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào:

Đầu ra: 9

Giải thích:

Tất cả các nút bên phải là:{2, 8, 9}. Tối đa là 9.

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, chúng ta cần đi ngang qua cái cây và kiểm tra xem con bên phải của nó có tồn tại hay không. Nếu nó tồn tại, hãy so sánh với phần tử maxRight và thay thế nếu nó lớn hơn.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

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

Đầu ra

The maximum among all right nodes in Binary Tree is 9