C++ 이진 트리에서 최댓값(또는 최솟값) 찾기

문제 개요

이 문제에서는 하나의 이진 트리(Binary Tree)가 주어지며, 우리의 과제는 이진 트리에서 최댓값(또는 최솟값)을 찾는 것입니다.

문제 설명: 이진 트리를 구성하는 노드들 중에서 값이 가장 큰 노드와 가장 작은 노드를 찾아야 합니다.

예시를 통해 문제를 이해해 보겠습니다.

입력:

출력: max = 9, min = 1

해결 접근 방법

이진 트리에서 최댓값을 가진 노드를 찾아야 합니다. 루트 노드에서 시작해 재귀적으로 왼쪽과 오른쪽 서브트리를 순회하고, 리프 노드에 도달할 때까지 탐색을 반복하면서 각 노드의 값을 비교하여 트리 전체의 최댓값을 구합니다.

핵심 아이디어는 다음과 같습니다.

• 현재 노드가 NULL이면 매우 작은 값을 반환합니다.
• 현재 노드의 값, 왼쪽 서브트리의 최댓값, 오른쪽 서브트리의 최댓값 세 값 중 가장 큰 값을 선택합니다.
• 이 과정을 재귀적으로 수행하면 트리 전체의 최댓값을 얻을 수 있습니다.

최솟값을 찾을 때도 동일한 방식을 사용하며, 비교 조건만 반대로 바꾸면 됩니다. 이 알고리즘은 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)입니다.

풀이 코드

다음은 위에서 설명한 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

예제

#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* NewRoot = NULL;
    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