문제 개요
이진 트리가 하나 주어져 있고, 이 트리를 오른쪽 측면에서 바라본다고 가정해 봅시다. 그러면 각 깊이(레벨)마다 가장 오른쪽에 위치한 노드만 눈에 보이게 됩니다. 이 문제의 목표는 그렇게 보이는 노드들의 값을 순서대로 출력하는 것입니다.
예를 들어 다음과 같은 트리가 있다고 합시다.
이 트리를 오른쪽에서 보면 레벨 순서대로 1 → 3 → 4가 차례로 보입니다.
접근 방법: DFS(깊이 우선 탐색) 활용
이 문제는 깊이 우선 탐색(DFS)으로 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 오른쪽 자식을 왼쪽 자식보다 먼저 방문하는 것입니다. 그러면 각 레벨에서 가장 먼저 도달하는 노드가 곧 해당 레벨의 가장 오른쪽 노드가 됩니다.
구체적인 절차는 다음과 같습니다.
- 트리 노드, 정답을 담을 배열, 현재 레벨을 매개변수로 받는
dfs()헬퍼 함수를 만듭니다. 초기 레벨은 0입니다. - 노드가 null이면 즉시 반환합니다.
- 현재 레벨이 정답 배열의 길이와 같다면, 해당 레벨을 처음 방문한 것이므로 노드의 값을 정답 배열에 추가합니다.
- 오른쪽 자식부터, 그다음 왼쪽 자식 순으로 재귀 호출하면서 레벨을 1씩 증가시킵니다.
- 메인 함수에서는 루트 노드와 빈 배열을 인자로
dfs(root, ans)를 호출합니다.
오른쪽을 먼저 탐색하기 때문에 "현재 레벨 == 정답 배열 크기" 조건을 만족하는 순간은 항상 그 레벨에서 가장 오른쪽에 있는 노드를 처음 만나는 시점입니다. 따라서 별도의 정렬이나 필터링 없이 자연스럽게 오른쪽 보기 결과가 완성됩니다.
C++ 구현 예제
#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;
}
};
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:
void dfs(TreeNode* node, vector <int>& ans, int level = 0){
if(!node) return;
if(level == ans.size())ans.push_back(node->val);
dfs(node->right, ans, level + 1);
dfs(node->left, ans, level + 1);
}
vector<int> rightSideView(TreeNode* root) {
vector <int> ans;
dfs(root, ans);
return ans;
}
};
main(){
vector<int> v = {1,2,3,NULL,5,NULL,4};
TreeNode *root = make_tree(v);
Solution ob;
print_vector(ob.rightSideView(root));
}입력
[1,2,3,null,5,null,4]
출력
[1, 3, 4]
복잡도 분석
시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이 h에 비례하며, 균형 잡힌 트리라면 O(log n)입니다.