문제 소개
이진 탐색 트리(Binary Search Tree, BST)와 하나의 목표값(target)이 주어졌을 때, 트리 내에 존재하는 두 원소의 합이 목표값과 같아지는 경우가 있는지 확인하는 문제입니다.
예를 들어 아래와 같은 BST가 입력으로 주어지면,
목표값이 9일 때 5+4=9 또는 6+3=9가 성립하므로 출력은 True가 됩니다.
해결 전략
이 문제는 크게 두 단계로 나누어 접근할 수 있습니다.
- 중위 순회(Inorder Traversal): BST를 중위 순회하면 값들이 오름차순으로 정렬된 배열을 얻을 수 있습니다.
- 투 포인터(Two Pointer): 정렬된 배열의 양 끝에서부터 포인터를 이동시키며, 합이 목표값이 되는 두 수를 효율적으로 찾습니다.
알고리즘 단계
- 배열 v를 정의합니다.
- 루트 노드를 매개변수로 받는 inorder() 함수를 정의합니다.
- 루트가 null이면 그대로 return 합니다.
- inorder(루트의 왼쪽 자식)을 재귀 호출합니다.
- 루트의 값을 배열 v에 삽입합니다.
- inorder(루트의 오른쪽 자식)을 재귀 호출합니다.
- k를 매개변수로 받는 findnode() 함수를 정의합니다.
- n := 배열 v의 크기로 설정하고, i = 0, j = n-1로 초기화합니다.
- i < j인 동안 다음을 반복합니다.
- t := v[i] + v[j]
- t == k이면 true를 반환합니다.
- t < k이면 i를 1 증가시킵니다.
- 그 외의 경우에는 j를 1 감소시킵니다.
- 반복문이 종료되면 false를 반환합니다.
- 메인 메서드에서는 다음 순서로 처리합니다.
- inorder(root)를 호출해 트리의 모든 값을 배열에 저장합니다.
- 배열 v를 정렬합니다.
- findnode(k)의 결과를 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}
else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}
else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
vector<int> v;
void inorder(TreeNode* root){
if (root == NULL || root->val == 0)
return;
inorder(root->left);
v.push_back(root->val);
inorder(root->right);
}
bool findnode(int k){
int n = v.size(), i = 0, j = n - 1;
while (i < j) {
int t = v[i] + v[j];
if (t == k)
return true;
if (t < k)
i++;
else
j--;
}
return false;
}
bool findTarget(TreeNode* root, int k){
inorder(root);
sort(v.begin(), v.end());
return findnode(k);
}
};
main(){
Solution ob;
vector<int> v = {5,3,6,2,4,NULL,7};
TreeNode *root = make_tree(v);
cout << (ob.findTarget(root, 9));
}
입력 및 출력
입력:
{5,3,6,2,4,NULL,7}, 9
출력:
1
출력값 1은 true를 의미합니다. 즉, 트리 안에 합이 9가 되는 두 노드(예: 5와 4, 또는 6과 3)가 실제로 존재한다는 뜻입니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n log n) — 중위 순회와 투 포인터 탐색은 각각 O(n)이지만, 정렬 과정에서 O(n log n)이 추가로 소요됩니다. 참고로 BST의 중위 순회 결과는 이미 오름차순으로 정렬되어 있으므로, 정렬 단계를 생략하면 O(n)까지 최적화할 수 있습니다.
- 공간 복잡도: O(n) — 트리의 모든 값을 저장할 배열과 재귀 호출 스택이 필요합니다.