ค้นหาโหนดสูงสุดใน Binary Tree ใน C++

ในปัญหานี้ เราได้รับ Binary Tree งานของเราคือ ค้นหาโหนดที่เหมาะสมที่สุดใน Binary Tree

คำอธิบายปัญหา: ที่นี่ เราต้องหาค่าสูงสุดจากโหนดย่อยที่ถูกต้องทั้งหมดของไบนารีทรี

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล:

ผลลัพธ์: 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