문제 이해하기
이진 트리가 하나 주어져 있습니다. 루트 노드는 깊이(depth) 0에 위치하며, 깊이 k에 있는 노드의 자식 노드들은 깊이 k+1에 존재합니다.
여기서 두 노드가 사촌(cousin) 관계라고 하는 것은, 두 노드가 같은 깊이에 있으면서 서로 다른 부모 노드를 가질 때를 의미합니다.
트리의 모든 값은 중복 없이 유일하며, 트리 내 서로 다른 두 노드의 값 x와 y가 주어집니다. 우리가 해야 할 일은 값 x와 y에 해당하는 노드들이 사촌 관계인지 여부를 확인하는 것입니다.
예를 들어 입력이 다음과 같다면,
x = 5, y = 4일 때 두 노드는 같은 깊이 2에 있고 부모가 서로 다르므로 출력 결과는 true가 됩니다.
해결 접근 방법
이 문제는 BFS(너비 우선 탐색) 기반의 레벨 순회(level order traversal)로 효과적으로 해결할 수 있습니다. 각 레벨을 순회하면서 목표 값(x, y)을 발견하면 해당 노드의 부모를 기록하고, 같은 레벨에서 두 값이 모두 발견되었을 때 부모가 다른지 비교하는 방식입니다.
구체적인 단계는 다음과 같습니다.
- 정수 값을 키로, TreeNode 포인터를 값으로 가지는 맵(map) um을 하나 정의합니다.
- TreeNode 포인터를 담는 큐(queue) q를 하나 정의합니다.
- 루트 노드를 큐에 삽입합니다.
- um[x]와 um[y]를 NULL로 초기화합니다.
- 큐가 빌 때까지 다음 과정을 반복합니다.
- 현재 큐의 크기를 qSize에 저장합니다. (현재 레벨의 노드 수)
- qSize가 0보다 클 동안 반복하며 매번 qSize를 1씩 감소시킵니다.
- cur을 큐의 첫 번째 원소로 설정한 후 큐에서 제거(pop)합니다.
- cur의 왼쪽 자식이 존재하는 경우
- um에 왼쪽 자식의 값이 이미 있다면(즉, x 또는 y라면), um[왼쪽 자식 값] := cur로 부모를 기록합니다.
- 그렇지 않다면 왼쪽 자식을 큐에 삽입합니다.
- cur의 오른쪽 자식도 같은 방식으로 처리합니다. um에 해당 값이 있으면 부모를 기록하고, 없으면 큐에 삽입합니다.
- 현재 레벨 순회가 끝난 후 um[x] 또는 um[y]가 0이 아니라면(두 값 중 하나 이상을 찾았다면)
- um[x]가 0이거나 um[y]가 0이거나(같은 레벨에서 둘 다 발견되지 않음), um[x]와 um[y]가 같다면(부모가 동일함) false를 반환합니다.
- 그 외의 경우에는 true를 반환합니다.
- 루프가 종료될 때까지 조건이 만족되지 않으면 false를 반환합니다.
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
bool isCousins(TreeNode *root, int x, int y) {
unordered_map<int, TreeNode *> um;
queue<TreeNode *> q;
q.push(root);
um[x] = um[y] = NULL;
while (!q.empty()) {
int qSize = q.size();
while (qSize-- > 0) {
auto cur = q.front();
q.pop();
if (cur->left && cur->left->val != 0)
if (um.count(cur->left->val))
um[cur->left->val] = cur;
else
q.push(cur->left);
if (cur->right && cur->right->val != 0)
if (um.count(cur->right->val))
um[cur->right->val] = cur;
else
q.push(cur->right);
}
if (um[x] or um[y])
if (!um[x] or !um[y] or um[x] == um[y])
return false;
else
return true;
}
return false;
}
};
main() {
Solution ob;
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2); root->right = new TreeNode(3);
root->left->right = new TreeNode(4); root->right->right = new TreeNode(5);
cout << (ob.isCousins(root, 5, 4));
}입력
TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(4); root->right->right = new TreeNode(5); cout << (ob.isCousins(root, 5, 4));
출력
1