문제 개요
균형 잡힌 이진 탐색 트리(BST)와 목표 합(target sum)이 주어졌을 때, 두 노드 값의 합이 목표 합과 일치하는 쌍(pair)이 존재하는지 확인하는 메서드를 구현해야 합니다. 이때 트리는 불변(immutable)이라는 점, 즉 트리의 구조나 값을 변경할 수 없다는 조건을 반드시 기억해야 합니다.
예를 들어 다음과 같은 트리가 입력으로 주어진다고 가정해 보겠습니다.
이 경우 출력 결과는 (9 + 26 = 35)가 됩니다.
해결 접근 방법
이 문제는 BST의 순회 특성을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 정렬된 배열의 양 끝에서 포인터를 안쪽으로 좁혀 가는 '투 포인터(two pointer)' 기법을 트리에 적용하는 것입니다.
구체적으로는 두 개의 독립적인 순회를 동시에 수행합니다.
- 정방향 순회(중위 순회): 가장 작은 값부터 오름차순으로 노드를 하나씩 방문합니다.
- 역방향 순회(역중위 순회): 가장 큰 값부터 내림차순으로 노드를 하나씩 방문합니다.
각 순회 상태는 스택을 사용하여 저장하며, 두 값의 합을 목표 합과 비교하면서 포인터를 이동시킵니다.
알고리즘 단계
- 두 개의 스택 s1, s2를 선언합니다.
- 플래그 변수 done1 := false, done2 := false로 초기화합니다.
- val1 := 0, val2 := 0으로 초기화합니다.
- curr1 := root, curr2 := root로 설정합니다.
- 무한 루프를 수행합니다.
- 정방향 순회: done1이 false인 동안, curr1이 NULL이 아니면 curr1을 s1에 삽입하고 왼쪽 자식으로 이동합니다. curr1이 NULL이면 s1이 비어 있는 경우 done1을 true로 설정하고 종료하며, 그렇지 않으면 스택 최상단 노드를 꺼내 val1에 저장한 뒤 curr1을 오른쪽 자식으로 이동하고 done1을 true로 설정합니다.
- 역방향 순회: done2가 false인 동안, 위 과정을 대칭으로 수행합니다. curr2가 NULL이 아니면 s2에 삽입하고 오른쪽 자식으로 이동하고, NULL이면 스택에서 노드를 꺼내 val2에 저장한 뒤 왼쪽 자식으로 이동합니다.
- val1 ≠ val2이고 (val1 + val2) == target이면 해당 쌍을 출력하고 true를 반환합니다.
- (val1 + val2) < target이면 더 큰 값이 필요하므로 done1 := false로 설정하여 정방향 순회를 진행합니다.
- (val1 + val2) > target이면 더 작은 값이 필요하므로 done2 := false로 설정하여 역방향 순회를 진행합니다.
- val1 ≥ val2이면 두 순회가 교차한 것이므로 더 이상 가능한 쌍이 없어 false를 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 100
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
bool isPairPresent(TreeNode* root, int target) {
stack<TreeNode*> s1, s2;
bool done1 = false, done2 = false;
int val1 = 0, val2 = 0;
TreeNode *curr1 = root, *curr2 = root;
while (true) {
while (done1 == false) {
if (curr1 != NULL) {
s1.push(curr1);
curr1 = curr1->left;
}
else {
if (s1.empty())
done1 = 1;
else {
curr1 = s1.top();
s1.pop();
val1 = curr1->val;
curr1 = curr1->right;
done1 = 1;
}
}
}
while (done2 == false) {
if (curr2 != NULL) {
s2.push(curr2);
curr2 = curr2->right;
}
else {
if (s2.empty())
done2 = 1;
else {
curr2 = s2.top();
s2.pop();
val2 = curr2->val;
curr2 = curr2->left;
done2 = 1;
}
}
}
if ((val1 != val2) && (val1 + val2) == target) {
cout << "Pair Found: " << val1 << " + " << val2 << " = " << target << endl;
return true;
}
else if ((val1 + val2) < target)
done1 = false;
else if ((val1 + val2) > target)
done2 = false;
if (val1 >= val2)
return false;
}
}
int main() {
TreeNode* root = new TreeNode(16);
root->left = new TreeNode(11);
root->right = new TreeNode(21);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(13);
root->right->left = new TreeNode(17);
root->right->right = new TreeNode(26);
int target = 35;
cout << (isPairPresent(root, target));
}입력
TreeNode* root = new TreeNode(16); root->left = new TreeNode(11); root->right = new TreeNode(21); root->left->left = new TreeNode(9); root->left->right = new TreeNode(13); root->right->left = new TreeNode(17); root->right->right = new TreeNode(26);
출력
Pair Found: 9 + 26 = 35 1
복잡도 분석
- 시간 복잡도: O(n) — 각 순회는 트리의 모든 노드를 최대 한 번씩만 방문합니다.
- 공간 복잡도: O(h) — h는 트리의 높이이며, 두 개의 스택에는 각 순회 경로의 노드만 저장됩니다.
트리를 배열로 변환하지 않고도 O(h)의 추가 메모리만으로 문제를 해결할 수 있다는 점에서, 이 방법은 불변 BST 환경에서 매우 효율적인 접근 방식입니다.