หาค่าสูงสุดและต่ำสุดใน Binary Tree ใน C++

โจทย์

ได้รับ Binary Tree ทางเราต้อง หาค่าสูงสุดและต่ำสุดใน Binary Tree

ตัวอย่าง

Input: ต้นไม้ดังภาพ (โหนดมีค่า 1, 2, 3, 5, 6, 8, 9)

Output: max = 9, min = 1

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

ท่องต้นไม้แบบ Post-order (หรือ Pre-order ก็ได้) เพื่อหาค่าสูงสุดและต่ำสุด:

• ถ้าโหนดเป็น NULL คืนค่าที่เหมาะสม (เช่น -INF สำหรับ max, INF สำหรับ min)
• เปรียบเทียบค่าของโหนดปัจจุบันกับค่าสูงสุด/ต่ำสุดของซับต้นไม้ซ้ายและขวา

โปรแกรมตัวอย่าง (หาค่าสูงสุด)

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

int findMaxNode(Node* root) {
    if (root == NULL) return -100;
    int maxVal = root->data;
    int leftMaxVal = findMaxNode(root->left);
    int rightMaxVal = findMaxNode(root->right);
    if (leftMaxVal > maxVal) maxVal = leftMaxVal;
    if (rightMaxVal > maxVal) maxVal = rightMaxVal;
    return maxVal;
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(8);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    cout << "The Maximum element of Binary Tree is " << findMaxNode(root) << endl;
    return 0;
}

ผลลัพธ์

The Maximum element of Binary Tree is 9