문제 설명
균형 잡힌 이진 탐색 트리(Binary Search Tree, BST)가 하나 주어져 있다고 가정해 보겠습니다. 우리는 is_valid_triplet()이라는 함수를 작성해야 합니다. 이 함수는 트리 내부에 합이 0이 되는 세 개의 노드(트리플렛)가 존재하면 true를, 존재하지 않으면 false를 반환합니다.
이 문제를 풀 때 반드시 지켜야 할 제약 조건은 다음과 같습니다.
- 기대 시간 복잡도는 O(n²)입니다.
- 추가로 사용할 수 있는 공간은 O(log n)입니다.
예를 들어 입력 트리가 다음과 같다고 해보겠습니다.
이 경우 출력은 True입니다. 노드 값 -15, 7, 8의 합이 정확히 0이 되는 트리플렛 [-15, 7, 8]이 존재하기 때문입니다.
해결 전략
이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.
- BST를 정렬된 이중 연결 리스트로 변환 — 중위 순회(in-order traversal)를 활용하면 BST의 모든 노드를 오름차순으로 정렬된 이중 연결 리스트로 바꿀 수 있습니다.
- 투 포인터(Two Pointer) 기법 적용 — 정렬된 리스트에서 음수 노드를 하나씩 고정한 뒤, 남은 구간에서 두 포인터를 움직여 고정된 값의 절댓값과 같은 합을 만드는 두 노드를 찾습니다.
1단계: bst_to_doubli_list() — BST를 이중 연결 리스트로 변환
이 함수는 재귀적으로 중위 순회를 수행하며 노드들을 이중 연결 리스트로 연결합니다. 동작 과정은 다음과 같습니다.
- root가 NULL이면 그대로 종료합니다.
- 왼쪽 서브트리를 먼저 처리합니다.
- 현재 노드의 left 포인터를 tail에 연결합니다.
- tail이 NULL이 아니라면 tail의 right를 현재 노드에 연결하고, NULL이라면(첫 번째 노드라면) head를 현재 노드로 설정합니다.
- tail을 현재 노드로 갱신한 뒤 오른쪽 서브트리를 처리합니다.
2단계: is_in_double_list() — 두 포인터로 목표 합 찾기
정렬된 이중 연결 리스트 위에서 head와 tail 두 포인터를 양 끝에 두고 목표 합(sum)을 만족하는 노드 쌍이 있는지 확인합니다.
- head와 tail이 만날 때까지 반복합니다.
- current = head의 key + tail의 key를 계산합니다.
- current == sum이면 true를 반환합니다.
- current > sum이면 합을 줄이기 위해 tail을 왼쪽으로 이동합니다.
- current < sum이면 합을 늘리기 위해 head를 오른쪽으로 이동합니다.
- 반복이 끝나면 조건을 만족하는 쌍이 없으므로 false를 반환합니다.
메인 로직: is_valid_triplet()
- 트리가 비어 있으면 false를 반환합니다.
- BST를 이중 연결 리스트로 변환합니다.
- head(가장 작은 값)부터 시작해, head의 right가 tail이 아니고 head의 key가 음수인 동안 다음을 반복합니다.
- head를 제외한 나머지 구간에서 -(head의 key)와 같은 합을 만드는 두 노드가 있는지 검사합니다. 찾으면 true를 반환하고, 못 찾으면 head를 오른쪽으로 한 칸 이동합니다.
- 모든 후보를 확인한 뒤에도 찾지 못하면 false를 반환합니다.
시간 복잡도를 살펴보면, 리스트 변환에 O(n)이 걸리고 각 노드마다 투 포인터 탐색에 최대 O(n)이 소요되므로 전체 O(n²)이 됩니다. 또한 균형 잡힌 트리에서 재귀 호출 스택의 깊이가 O(log n)이므로 추가 공간 제약 조건 역시 만족합니다.
C++ 구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int key;
TreeNode *left;
TreeNode *right;
TreeNode() : key(0), left(NULL), right(NULL) {}
TreeNode(int x) : key(x), left(NULL), right(NULL) {}
};
void bst_to_doubli_list(TreeNode* root, TreeNode** head, TreeNode** tail) {
if (root == NULL)
return;
if (root->left)
bst_to_doubli_list(root->left, head, tail);
root->left = *tail;
if (*tail)
(*tail)->right = root;
else
*head = root;
*tail = root;
if (root->right)
bst_to_doubli_list(root->right, head, tail);
}
bool is_in_double_list(TreeNode* head, TreeNode* tail, int sum) {
while (head != tail) {
int current = head->key + tail->key;
if (current == sum)
return true;
else if (current > sum)
tail = tail->left;
else
head = head->right;
}
return false;
}
bool is_valid_triplet(TreeNode *root) {
if (root == NULL)
return false;
TreeNode* head = NULL;
TreeNode* tail = NULL;
bst_to_doubli_list(root, &head, &tail);
while ((head->right != tail) && (head->key < 0)){
if (is_in_double_list(head->right, tail, -1*head->key))
return true;
else
head = head->right;
}
return false;
}
TreeNode* insert(TreeNode* root, int key) {
if (root == NULL)
return new TreeNode(key);
if (root->key > key)
root->left = insert(root->left, key);
else
root->right = insert(root->right, key);
return root;
}
int main(){
TreeNode* root = NULL;
root = insert(root, 7);
root = insert(root, -15);
root = insert(root, 15);
root = insert(root, -7);
root = insert(root, 14);
root = insert(root, 16);
root = insert(root, 8);
cout << is_valid_triplet(root);
}입력
root = insert(root, 7); root = insert(root, -15); root = insert(root, 15); root = insert(root, -7); root = insert(root, 14); root = insert(root, 16); root = insert(root, 8);
출력
1
출력값 1은 true를 의미하며, 합이 0이 되는 트리플렛이 실제로 존재함을 나타냅니다.