หาค่าสูงสุดในโหนดขวาของ Binary Tree ใน C++

โจทย์

ได้รับ Binary Tree ทางเราต้อง หาค่าสูงสุดในโหนดขวาทั้งหมดของ Binary Tree

ตัวอย่าง

Input: ต้นไม้ดังภาพ (โหนดขวาคือ 2, 8, 9)

Output: 9

แนวทางแก้ปัญหา

ท่องต้นไม้ (Tree Traversal) ตรวจสอบว่าโหนดขวา (right child) มีอยู่หรือไม่ ถ้ามี ให้เปรียบเทียบกับค่าสูงสุดที่พบจนถึงตอนนั้น และอัปเดตค่าสูงสุด

โปรแกรมตัวอย่าง

#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