이진 트리가 하나 주어졌다고 가정해 봅시다. 이 트리를 왼쪽에서 바라보면 특정 노드들만 보이게 되는데, 우리는 그 보이는 노드들을 출력해야 합니다.
예를 들어 트리가 다음과 같다면 −
출력 결과는 [1, 2, 5]가 됩니다. 왼쪽에서 볼 때 루트 노드 1, 두 번째 깊이에서 가장 왼쪽에 있는 노드 2, 세 번째 깊이에서 가장 왼쪽에 있는 노드 5만 보이기 때문입니다.
접근 방법
이 문제는 DFS(깊이 우선 탐색)와 깊이(depth) 추적을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 깊이에서 가장 먼저 방문되는 노드가 곧 왼쪽 뷰에 해당한다는 점입니다. 왼쪽 자식을 오른쪽 자식보다 먼저 탐색하기 때문입니다.
해결 절차는 다음과 같습니다 −
- 결과를 저장할 배열
ret을 정의합니다. - 매개변수로 노드(
node)와 현재 깊이(c, 기본값 1)를 받는dfs()함수를 정의합니다. node가 null이면 함수를 종료(return)합니다.c > lvl이라면, 즉 현재 깊이가 지금까지 방문한 최대 깊이보다 크다면 −lvl := c로 최대 깊이를 갱신합니다.- 현재 노드의 값을
ret에 삽입합니다.
dfs(node의 왼쪽 자식, c + 1)을 재귀 호출합니다.dfs(node의 오른쪽 자식, c + 1)을 재귀 호출합니다.- 메인 함수에서는 다음을 수행합니다 −
lvl := -1로 초기화합니다.dfs(root, 0)을 호출합니다.ret을 반환합니다.
시간 복잡도는 모든 노드를 한 번씩 방문하므로 O(N)이며, 공간 복잡도는 재귀 호출 스택으로 인해 최악의 경우 O(N)입니다.
구현 예제
다음 코드를 통해 더 자세히 이해해 보겠습니다 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
class Solution {
public:
vector <int> ret;
int lvl;
void dfs(TreeNode* node, int c = 1){
if(!node)
return;
if(c > lvl){
lvl = c;
ret.push_back(node->val);
}
dfs(node->left, c + 1);
dfs(node->right, c + 1);
}
vector<int> solve(TreeNode* root) {
lvl = -1;
dfs(root, 0);
return ret;
}
};
main(){
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);
Solution ob;
print_vector(ob.solve(root));
}입력
TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->right = new TreeNode(5); root->right->right = new TreeNode(4);
출력
[1,2,5]
위 코드에서 dfs() 함수는 왼쪽 자식을 먼저 방문하므로, 각 깊이에 도달하는 첫 번째 노드가 항상 해당 깊이에서 가장 왼쪽에 있는 노드가 됩니다. 조건 c > lvl은 같은 깊이의 노드가 여러 번 기록되지 않도록 중복을 방지하는 역할을 합니다.