Tìm giá trị lớn nhất giữa các nút con phải trong cây nhị phân C++

Cho một cây nhị phân. Nhiệm vụ: tìm giá trị lớn nhất giữa tất cả các nút con phải.

Mô tả bài toán: Cần tìm giá trị lớn nhất trong tập các nút con phải của cây nhị phân.

Ví dụ:

Đầu vào:

Đầu ra: 9

Giải thích:

Các nút con phải: {2, 8, 9}. Max = 9.

Phương pháp giải

Duyệt cây, kiểm tra nếu nút con phải tồn tại thì so sánh với maxRight và cập nhật nếu lớn hơn.

Chương trình minh họa

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

Kết quả

The maximum among all right nodes in Binary Tree is 9