[LeetCode] 199. Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view

개요

1. 이진 트리의 root 노드가 주어진다.
   • 노드의 개수는 0개에서 100개
2. 이진 트리를 오른쪽에서 바라봤을 때 볼 수 있는 노드를 구해라

문제 해결 아이디어

• 특정 뎁스의 최우측에 위치한 노드들을 구하면 된다.
  ➡️ 뎁스 단위로 최우측에 있는 노드가 어떤 노드인지 확인해야 한다.
  ➡️ 특정 뎁스 당 하나의 노드이므로, <인덱스, 노드>로 이루어진 HashMap 을 활용할 수 있다.
  

🧐 BFS(Breath First Search)를 이용하자

의사 코드

1. 큐에 루트 노드를 삽입한다.
2. 큐의 사이즈를 구한다.
3. 큐에서 루트 노드를 삭제한다.
4. 루트 노드의 left 노드를 큐에 삽입한다.
5. 루트 노드의 right 노드를 큐에 삽입한다.
6. key : depth, value : 루트 노드의 값 을 HashMap에 삽입한다.
7. depth 값을 1 증가시킨다.

while(큐가 비어있지 않음){
	int size = 큐 사이즈;
    for(int i=0 부터 size까지){
    	TreeNode n = 큐.remove();
        map.put(뎁스, n.값);
        do 큐에 자식 노드 삽입;
    }
    뎁스++;
}

DFS로 풀이하기

BFS로 풀이해도 결국 트리의 뎁스를 알지 못하고, 이전 노드를 통해 하위 노드에 접근해야 하기 때문에 모든 노드를 순회해야 한다.
따라서 DFS로 풀이해도 성능이 동일할 것이라고 생각해 DFS로 풀이해보았다.

1. 전역 변수 map을 사용한다.
2. <depth-현재 노드의 값> 엔트리가 map에 삽입된다.
3. 현재 노드에 왼쪽 하위 노드가 있다면 왼쪽 하위 노드로 이동하고 depth + 1 이 된다.
4. <depth-하위 노드의 값> 엔트리가 map에 삽입된다.
   3-1. 하위 노드가 null 일때까지 하위 노드로 이동하며 map에 값이 추가된다.
5. 현재 노드에 오른쪽 하위 노드가 있다면 오른쪽 하위 노드로 이동하고 depth + 1이 된다.
6. <depth-하위 노드의 값> 엔트리가 map에 삽입된다.
   5-1. 기존에 key로 depth 값이 있다면 갱신된다.

void recursive(TreeNode 노드, int 뎁스){
	map.put(뎁스, 노드.val)
    if(node.left != null) recursive(node.left, 뎁스 + 1);
    if(node.right != null) recursive(node.right, 뎁스 + 1);
}

결과

전체 코드 github 링크

다른 풀이

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }
    
    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }
        
        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);
        
    }

이 문제는 BFS로 풀이하는 것보다 DFS로 풀이하는 게 시간복잡도가 더 개선된 결과로 나왔다.

위의 문제 풀이 방식은 나의 DFS 풀이와 동일한 것 같다.
그런데 나처럼 Map을 굳이 활용하지 않고, List를 처음부터 활용해서 result.size를 depth와 확인했다.
나의 풀이는 Map을 활용해 마지막에 ArrayList 화를 따로 하기 때문에 생기는 추가적인 복잡도가 있을 거 같다.
따라서 이 풀이가 더 효율적인 것 같다.