[Java] 199. Binary Tree Right Side View

문제 파악

주어지는 트리를, 오른쪽에서 바라보았을 때 보이는 노드들을 반환해야한다.

 

문제 해석 시, 약간 혼동이 있어서 처음에는 트리의 가장 오른쪽 노드들을 출력해야하는 줄 알았다.

 

따라서 위와 같이 구성된 트리의 경우, root 노드의 right node 는 없기 때문에 결과가 [1] 이 나와야 된다고 생각했는데

 

요구하는 답은 [1,2] 였다.

 

해석을 찾아보니, 이 트리를 오른쪽에서 바라봤을 때 보이는 노드들을 출력하라는 뜻이었다.

---

풀이

1️⃣ 전위 탐색을 이용한 풀이

전위 탐색

 

💡 떠오른 Idea

전위 탐색의 경우 위와 같이 루트 노드에서 시작하여 왼쪽 혹은 오른쪽 경로의 끝에 도달하면 부모의 반대편 노드로 넘어가는 방식으로 탐색한다.

위 문제의 경우는 가장 오른쪽을 탐색해야하므로

경로를 오른쪽으로 시작하도록 전위 탐색을 구현하면 되겠다고 판단하였다.

그리고 list 에 노드를 넣는 시점은 전위 탐색 메서드를 호출할 때 마다 depth 파라미터를 이용하여

depth 가 증가하지 않으면 추가하지 않는 방식으로 구현할 수 있었다.

 

import java.util.*;

class Solution {
    List<Integer> list = new ArrayList<>();
    int maxDepth = -1;

    public List<Integer> rightSideView(TreeNode root) {
        preOrder(root, 0);

        return list;
    }

    private void preOrder(TreeNode node, int depth) {
        if (node == null) {
            return;
        }

        if (depth > maxDepth) {
            list.add(node.val);
            maxDepth = depth;
        }

        preOrder(node.right, depth + 1);
        preOrder(node.left, depth + 1);

    }
}

 

결과

 

---

📖 회고

이전 문제는 중위 탐색을 이용하여 구현하였는데, 

 

이번 문제에서는 전위 탐색을 이용하여 풀이하였다.

 

따라서, 이 문제는 후위 탐색을 통해서 보이는 노드들을 우선적으로 추가해주고,

 

다른 노드에서 추가적인 depth 가 존재할 경우 추가해주는 방식으로 구현하면 되었다.