문제 소개
0부터 n-1까지 번호가 매겨진 n개의 이진 트리 노드가 주어졌다고 가정해 봅시다. 각 노드 i는 두 개의 자식을 가질 수 있으며, 왼쪽 자식은 leftChild[i], 오른쪽 자식은 rightChild[i]로 표현됩니다. 이때 주어진 모든 노드가 정확히 하나의 유효한 이진 트리를 이루는 경우에만 true를 반환해야 합니다.
노드 i에 왼쪽 자식이 없으면 leftChild[i]는 -1이 되고, 마찬가지로 오른쪽 자식이 없으면 rightChild[i]는 -1입니다. 또한 이 문제에서 노드는 실제 값을 가지지 않으며 노드 번호만 사용한다는 점을 기억해야 합니다.
예를 들어 입력이 다음과 같다면 -
출력은 true가 됩니다.
해결 전략
이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 유효한 이진 트리가 되려면 다음 두 조건을 만족해야 합니다.
- 사이클이 없어야 함 : 어떤 노드도 두 번 이상 방문되어서는 안 됩니다.
- 모든 노드가 연결되어야 함 : 루트에서 시작한 탐색만으로 모든 노드에 도달할 수 있어야 합니다.
여기서는 노드 0이 루트라고 가정하고 탐색을 시작합니다.
DFS 메서드 설계
- dfs라는 이름의 메서드를 정의합니다. 이 메서드는 노드 번호, leftChild, rightChild, visited 집합을 인자로 받습니다.
- 노드 n이 이미 visited에 포함되어 있다면 false를 반환합니다(사이클 감지).
- 노드 n을 visited 집합에 추가합니다.
- ret := true로 초기화합니다.
- n의 leftChild가 -1이 아니라면, ret := ret AND dfs(leftChild[node], leftChild, rightChild, visited)를 수행합니다.
- n의 rightChild가 -1이 아니라면, ret := ret AND dfs(rightChild[node], leftChild, rightChild, visited)를 수행합니다.
- ret을 반환합니다.
전체 검증 흐름
- ret := dfs(0, leftChild, rightChild, visited)를 호출해 노드 0부터 탐색을 시작합니다.
- 0부터 n-1까지 모든 노드를 확인하면서, 방문되지 않은 노드가 하나라도 있으면 false를 반환합니다(분리된 트리가 존재한다는 의미).
- 모든 조건을 통과하면 ret을 반환합니다.
C++ 구현 예제
아래 구현을 살펴보면 더 쉽게 이해할 수 있습니다 -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool dfs(int node, vector <int>& leftChild, vector <int>& rightChild, set <int>& visited){
if(visited.count(node)) return false;
visited.insert(node);
bool ret = true;
if(leftChild[node] != -1){
ret &= dfs(leftChild[node], leftChild, rightChild, visited);
}
if(rightChild[node] != -1){
ret &= dfs(rightChild[node], leftChild, rightChild, visited);
}
return ret;
}
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
set <int> visited;
bool ret = dfs(0, leftChild, rightChild, visited);
bool allVisited = true;
for(int i = 0; i < n; i++){
if(!visited.count(i))return false;
}
return ret;
}
};
main(){
vector<int> v1 = {1,-1,3,-1}, v2 = {2,-1,-1,-1};
Solution ob;
cout << (ob.validateBinaryTreeNodes(4, v1, v2));
}
입력
4 [1,-1,3,-1] [2,-1,-1,-1]
출력
1
복잡도 분석
시간 복잡도 : O(n) — 각 노드를 정확히 한 번씩만 방문합니다.
공간 복잡도 : O(n) — 방문 여부를 기록하는 집합과 재귀 호출 스택에 공간이 필요합니다.