199. Binary Tree Right Side View

난이도: 중간 (Medium)

링크: LeetCode 199

풀이날짜: 2025/10/03(못품), 2025/10/09(품)

 

---

1. 문제 이해

 

주어진 이진 트리에서, 오른쪽 측면에서 보이는 노드들의 값을 반환해야 하는 문제로,

각 레벨(level)마다 가장 오른쪽에 위치한 노드만 결과값으로 포함시켜야 한다.

---

2. 접근 방식 및 자료 구조

나는 DFS 방식으로 풀었으나, 문제 의도에는 BFS 방식이 더 적절해 보인다.

 

방법 1: DFS (오른쪽 우선 탐색) 

• 깊이(Depth)를 추적하면서 오른쪽 자식부터 탐색한다.
• 각 깊이에서 처음 방문한 노드가 그 레벨의 가장 오른쪽 노드가 된다.
• depth === result.length 조건을 통해 해당 깊이에서 아직 추가되지 않은 노드만 결과에 넣는다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
function rightSideView(root) {
  const result = [];

  function dfs(node, depth) {
    if (!node) return;

    // 해당 깊이에서 처음 방문한 노드라면 오른쪽 노드일 것이다.
    if (depth === result.length) {
      result.push(node.val);
    }

    // 오른쪽 → 왼쪽 순으로 탐색
    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  }

  dfs(root, 0);
  return result;
}

 

시간 복잡도: O(n) — 모든 노드를 한 번씩 방문

공간 복잡도: O(h) — 재귀 호출 스택 (h는 트리의 높이)

 

---

방법 2: BFS (레벨 탐색)

• 각 레벨의 노드를 모두 순회하되, 마지막 노드(i === len - 1) 의 값만 결과에 추가한다.
• 큐(Queue)를 사용해 레벨 단위로 탐색한다.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
  if (!root) return [];
  
  const result = [];
  const queue = [root];

  while (queue.length > 0) {    
    const len = queue.length;

    for (let i = 0; i < len; i++) {
      const node = queue.shift();

      // 해당 레벨의 마지막 노드만 추가
      if (i === len - 1) result.push(node.val);

      // 왼쪽, 오른쪽 순으로 추가 (BFS 순서 유지)
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }

  return result;
};

 

시간 복잡도: O(n) — 모든 노드를 한 번씩 방문

공간 복잡도: O(n) — 큐에 최대로 레벨 단위 노드들이 저장될 수 있음

 

---

3. 핵심 포인트 요약

구분	DFS	BFS
탐색 순서	오른쪽 → 왼쪽	레벨별 (좌 → 우)
추가 조건	depth === result.length	i === len - 1
장점	코드 간결, 재귀적 사고	명시적 구조, 디버깅 용이
공간 복잡도	O(h)	O(n)
공통점	각 레벨의 “오른쪽 끝” 노드만 결과에 추가

 

---

✅ 정리

이 문제는 두 가지 모두 유효한 접근법이 있으며,

• DFS는 “오른쪽부터 깊게 들어가며 한 레벨의 첫 노드만 기록”
• BFS는 “한 레벨을 모두 보고 마지막 노드만 기록”

한다는 점이 핵심이다.