C++에서 이진 트리의 후위 순회에서 n번째 노드 찾기

이 문제에서는 하나의 이진 트리(Binary Tree)와 정수 N이 주어지며, 트리를 후위 순회(Postorder Traversal)했을 때 N번째로 방문하게 되는 노드를 찾아 출력하는 것이 목표입니다.

이진 트리는 각 노드가 최대 두 개의 자식 노드만 가질 수 있다는 특수한 조건을 만족하는 트리 구조입니다.

순회(Traversal)란 트리에 속한 모든 노드를 체계적으로 방문하는 과정을 의미하며, 필요에 따라 방문한 노드의 값을 출력하기도 합니다.

예제로 문제 이해하기

입력

N = 6

출력

3

설명

위 트리의 후위 순회 결과는 다음과 같습니다.

4 → 5 → 2 → 6 → 7 → 3 → 1

후위 순회는 '왼쪽 자식 → 오른쪽 자식 → 루트' 순서로 노드를 방문합니다. 따라서 6번째로 방문되는 노드는 값이 3인 노드입니다.

풀이 접근 방법

이 문제는 재귀 호출을 이용한 후위 순회를 그대로 활용하면 쉽게 해결할 수 있습니다.

후위 순회에서는 각 호출마다 먼저 왼쪽 서브트리에 대해 postOrder()를 호출하고, 이어서 오른쪽 서브트리에 대해 postOrder()를 호출한 뒤, 마지막에 현재 노드(루트)를 방문합니다.

이 과정에서 지금까지 방문한 노드의 개수를 카운트하고, 카운트가 N과 일치하는 시점의 노드 값을 출력하면 됩니다.

구현 예제

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int nodeCount = 0;

void findNthPostorder(Node* root, int N) {
    if (root == nullptr)
        return;
    // 왼쪽 서브트리 순회
    findNthPostorder(root->left, N);
    // 오른쪽 서브트리 순회
    findNthPostorder(root->right, N);
    // 현재 노드 방문
    nodeCount++;
    if (nodeCount == N)
        cout << N << "번째 후위 순회 노드: " << root->data << endl;
}

int main() {
    /* 예제 트리 생성
              1
            /   \
           2     3
          / \   / \
         4   5 6   7
    */
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    int N = 6;
    findNthPostorder(root, N);
    return 0;
}

출력

6번째 후위 순회 노드: 3

복잡도 분석

시간 복잡도: O(N) — 트리의 모든 노드를 한 번씩 방문합니다.

공간 복잡도: O(H) — 재귀 호출 스택은 트리의 높이(H)에 비례하여 사용됩니다.