[알고리즘] LeetCode - Binary Tree Right Side View

Binary Tree Right Side View - LeetCode

문제 설명

• 이진 탐색 트리의 root 노드가 주어진다.
• 이진 탐색 트리의 오른쪽에서 봤을 때 보이는 모든 수를 찾아서 반환해야 한다.
• 트리의 레벨마다 가장 오른쪽에 위치한 노드의 수를 반환해야 한다.

문제 해결

• 노드의 개수가 0 ~ 100개 이기 때문에 최악의 경우라 해도 레벨은 최대 100까지 존재한다.
• dfs를 통해 깊이 우선 탐색을 진행하는데, 왼쪽부터 진행하고 오른쪽을 마지막에 진행한다.
• 각 탐색마다 현재 노드의 값을 정수형 배열 values에 현재 깊이를 인덱스로 저장한다. (현재 깊이가 2일 경우 values[2]에 저장)
• 왼쪽을 먼저 탐색하고 오른쪽을 탐색하기 때문에 values에 남은 값들은 각 깊이별 가장 오른쪽에 있는 값이 된다.
• 탐색을 마치고, 최대 깊이만큼 배열에서 값을 가져온다. (갱신한 범위만큼만)
• 정답 리스트를 생성해서 반환한다.

시간 복잡도

• O(N)
• 모든 노드를 방문하기 때문에 O(N)의 시간 복잡도를 가진다.

풀이 코드

class Solution {
    static int maxDepth;
    static int[] values;

    public List<Integer> rightSideView(TreeNode root) {
        maxDepth = 0;
        values = new int[101];
        List<Integer> answer = new ArrayList<>();

        if (root == null) {
            return answer;
        }

        dfs(root, 0);

        for (int i = 0; i <= maxDepth; i++) {
            answer.add(values[i]);
        }
        return answer;
    }

    static void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        maxDepth = Math.max(maxDepth, depth);
        values[depth] = root.val;

        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}

결과

시간	메모리
1 ms	41.2 MB