문제 개요
이 문제에서는 하나의 이진 트리와 특정 노드가 주어지며, 우리의 과제는 해당 노드의 후위 순회 후속자(postorder successor)를 찾아 출력하는 것입니다.
이진 트리란?
이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 특수한 트리 구조입니다.
후위 순회란?
후위 순회(Postorder Traversal)는 트리를 순회하는 기법 중 하나로, 먼저 왼쪽 서브트리를 순회한 다음 오른쪽 서브트리를 순회하고, 마지막에 루트(root)를 방문합니다.
위 트리의 후위 순회 결과: 8 4 2 7 9 6
예제로 이해하기
입력 − 위 예제의 이진 트리, 노드 = 7
출력 − 9
설명 − 이진 트리의 후위 순회 결과를 살펴보면 노드 7 다음에 방문되는 노드가 9임을 확인할 수 있습니다.
해결 접근 방법
단순한 방법
가장 직관적이고 간단한 방법은 트리 전체를 후위 순회한 뒤, 주어진 노드 바로 다음에 등장하는 값을 출력하는 것입니다.
하지만 우리는 더 효율적인 해결 방법을 알아볼 필요가 있습니다.
효율적인 방법
효율적인 해결책은 후위 순회의 일반적인 규칙에 대한 몇 가지 관찰을 활용하는 것입니다.
루트는 후위 순회에서 마지막으로 방문되는 노드이므로, 루트의 후속자는 NULL입니다.
현재 노드가 부모의 오른쪽 자식이라면, 부모 노드가 후속자입니다.
현재 노드가 왼쪽 자식이라면 다음과 같습니다.
오른쪽 형제 노드가 존재하지 않으면, 부모 노드가 후속자입니다.
오른쪽 형제 노드가 존재하면, 그 형제 노드 또는 형제 노드의 가장 왼쪽 자식이 후속자입니다.
이 방법은 매우 효율적이며, 시간 복잡도는 트리의 높이 h에 대해 O(h)입니다.
구현 예제
위에서 설명한 해결 방법을 구현한 C++ 프로그램입니다.
#include <iostream>
using namespace std;
struct Node {
struct Node *left, *right, *parent;
int value;
};
struct Node* insertNode(int value) {
Node* temp = new Node;
temp->left = temp->right = temp->parent = NULL;
temp->value = value;
return temp;
}
Node* findPostorderSuccessor(Node* root, Node* n) {
if (n == root)
return NULL;
Node* parent = n->parent;
if (parent->right == NULL || parent->right == n)
return parent;
Node* curr = parent->right;
while (curr->left != NULL)
curr = curr->left;
return curr;
}
int main(){
struct Node* root = insertNode(6);
root->parent = NULL;
root->left = insertNode(2);
root->left->parent = root;
root->left->left = insertNode(8);
root->left->left->parent = root->left;
root->left->right = insertNode(4);
root->left->right->parent = root->left;
root->right = insertNode(9);
root->right->parent = root;
root->right->left = insertNode(7);
root->right->left->parent = root->right;
root->left->right->left = insertNode(14);
struct Node* successorNode = findPostorderSuccessor(root, root->left->right);
if (successorNode)
cout<<"Postorder successor of "<<root->left->right->value<<" is "<<successorNode->value;
else
cout<<"Postorder successor of "<<root->left->right->value<<" is NULL";
return 0;
}출력
Postorder successor of 4 is 2
실행 결과를 보면 노드 4의 후위 순회 후속자는 2입니다. 이처럼 전체 트리를 순회하지 않고도 부모 포인터와 형제 노드의 위치 관계만으로 후속자를 빠르게 찾을 수 있습니다.