C++로 이진 트리의 모든 오른쪽 자식 노드 중 최대값 찾기

이 문제에서는 하나의 이진 트리(Binary Tree)가 주어지며, 우리의 목표는 트리에 있는 모든 오른쪽 자식 노드들 중에서 최대값을 찾는 것입니다.

문제 설명

주어진 이진 트리를 순회하면서 각 노드의 오른쪽 자식 노드 값들을 모두 수집하고, 그중 가장 큰 값을 구해야 합니다. 왼쪽 자식 노드의 값은 계산 대상에서 제외됩니다.

예시로 문제 이해하기

입력:

출력: 9

설명:

위 트리에서 오른쪽 자식 노드들은 {2, 8, 9}입니다. 이 중 가장 큰 값은 9입니다.

해결 접근 방법

이 문제는 재귀(Recursion)를 활용한 트리 순회로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 트리를 순회하면서 현재 노드의 오른쪽 자식이 존재하는지 확인합니다.
• 오른쪽 자식이 존재한다면, 해당 노드의 값을 지금까지 찾은 최대값(maxRight)과 비교하여 더 크면 갱신합니다.
• 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하며 최종적으로 전체 최대값을 반환합니다.

솔루션 구현 코드

아래는 위 접근 방법을 C++로 구현한 예제입니다.

#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

코드 동작 원리

findMaxRightNode 함수는 루트 노드부터 시작해 재귀적으로 트리를 탐색합니다. 각 호출 시점에서 현재 노드의 오른쪽 자식이 존재하면 그 값을 후보 최대값으로 설정하고, 왼쪽과 오른쪽 서브트리의 탐색 결과와 비교하여 가장 큰 값을 상위 호출로 반환합니다. 이 과정을 통해 트리 전체의 오른쪽 자식 노드 값 중 최대값이 도출됩니다.

이 알고리즘의 시간 복잡도는 트리의 모든 노드를 한 번씩 방문하므로 O(N)이며, 공간 복잡도는 재귀 호출 스택 깊이에 따라 최악의 경우 O(N)입니다.