leetcode top interview 150 | Binary Tree Right Side View | DFS

 

Question

 

트리구조로 된 노드들이 주어지고 트리를 오른쪽에서 봤을때 가장 오른쪽에 있는 노드의 value를 트리의 위부터 아래까지 순서대로 리스트에 넣어서 반환한다

 

 

Accepted Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 import java.util.*;
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list, 0);
        return list;
    }
    private static void dfs(TreeNode node, List<Integer> list, int depth){
        if(node == null)
            return;
        if(depth == list.size()){
            list.add(node.val); 
        }
        dfs(node.right, list, depth + 1);
        dfs(node.left, list, depth + 1);
    }
}

 

Solve

 

처음에 무조건 right 노드의 value만 저장되어 있어야 한다고 잘못읽었는데, 오른쪽에서 트리를 봤을때 가장 먼저 보이는 노드를 리스트에 넣어야한다. 

따라서 루트 정보가 아래처럼 주어졌을때에는 리스트에 [1, 3, 4]를 담아 반환해야한다. 

 

 

트리엔 레벨이 존재한다. 같은 깊이에 있는 노드들이 같은 레벨에 있는 노드들이다. 

예제를 보면 레벨 0인 루트노드부터 노드의 끝인 리프노드까지 레벨 별로 가장 오른쪽에 있는 노드 하나를 선별하여 리스트에 넣어야한다.

 

 

사전에 생각한 내용은 다음과 같다.

 

1. 루트 노드부터 가장 끝에 있는 노드까지 순차적으로 탐색하는 DFS 탐색으로 풀어야하고, 재귀를 통해 구현하자
2. 항상 기준은 오른쪽에 있는 노드부터 탐색해야한다.
3. 더 이상 right 노드가 없는데 left 노드 레벨이 right 노드의 레벨보다 높은 경우, left에 있는 노드를 넣어야하므로 right 노드의 끝까지 간 경우 다시 호출지점으로 돌아와서 left를 탐색하도록 해야한다.

 

따라서 노드번호를 담을 ArrayList를 생성하고 현재 시작하는 root노드의 depth를 저장할 변수와 함께 root노드를 dfs 함수로 넘긴다.

 

넘어온 노드가 null이면 탐색을 중지해야하기 때문에 기저조건으로 설정하고, right 부터 탐색을 하도록 root.right를 node로 넘겨 depth를 높인다. right 노드의 끝까지 가고 난 후 left를 호출하도록 해서 계속 dfs함수가 호출될 때마다 우선적으로 right 노드를 확인할 수 있도록 했다.

 

언제 list에 val값을 넣을지 고민했었는데, 트리 depth당 하나의 val을 넣어야하므로 depth가 현재 list의 size와 동일하면 넣도록 했다.

그렇게 하면 right노드를 탐색할 때마다 리스트에 val이 add되고, right이 없어서 left를 탐색하는 경우 depth가 right보다 깊은 경우만 add되게 할 수 있다.

 

 

위에 있는 root = [1,2,3,4]의 호출 순서는 아래와 같다.

 

 

1. dfs(root, list, 0) 루트 노드인 1을 방문하면서 dept == list size == 0으로 1을 리스트에 넣음

2. dfs(node.right, list, 1) 호출로 노드 3을 방문했을때 dept == list size == 1로 3을 리스트에 넣음

3. 노드 3의 right == null로 깊이 탐색이 끝나면 해당 프레임이 pop 되고, 다시 dfs(root, list, 0)의 상태가 됨

4. dfs(root.left, list, 1)을 호출하면서 노드 2를 방문했을때 dept == 1 != list size == 1이라서 2를 넣지않고

5. 노드2의 right == null로 right탐색이 끝나면 pop하고 dfs(node.left, list, 2)를 호출함

6. 노드4를 방문했을때 dept == list size == 2로 4를 리스트에 넣음

7. dfs(node.right, list, 3)을 호출하지만 root == null이라서 pop하고 dfs(node.left, list, 3)도 null이라 pop하게 되면서 로직이 끝난다.

 

 

https://leetcode.com/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=top-interview-150 

Binary Tree Right Side View - LeetCode