[LeetCode] 199. Binary Tree Right Side View

Binary Tree Right Side View - LeetCode

이진 트리의 루트가 주어졌을 때, 자신이 그 오른쪽에 서 있다고 상상하고
위에서 아래로 순서대로 보이는 노드의 값을 반환합니다.

 

Example 1:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

Example 2:

Input: root = [1,null,3]
Output: [1,3]

Example 3:

Input: root = []
Output: []

 

문제 접근

노드의 오른쪽만 방문하면 되겠다고 생각했습니다.

 

단순히 DFS를 이용해 탐색을 할때 오른쪽 노드만 방문하고

방문할때 각 노드의 값들을 먼저 저장해주면 됩니다.

 

List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        traverse(root);
        return res;
    }

    public void traverse(TreeNode root) {
        if (root == null) return;

        res.add(root.val);
        traverse(root.right);
    }

 

하지만 예외 케이스를 전부 캐치하지는 못했습니다.

그 이유는 오른쪽 노드가 없을때는 왼쪽노드가 보여야하기 때문입니다.

2번째 도전

도저히 방법이 떠오르지 않아 다른사람의 풀이를 참고하였습니다.

 

해결 방법은 depth를 사용하는것입니다.

만약 depth와 list의 사이즈가 갖다면 오른쪽에서 바라보는 첫번째 값인것입니다.

이것이 가능한 이유는 오른쪽부터 탐색하기 때문입니다.

만약 오른쪽이 없다면, 왼쪽의 노드가 선택이 됩니다.

 

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> rightSideView(TreeNode root) {
        traverse(root, 0);
        return res;
    }

    public void traverse(TreeNode root, int depth) {
        if (root == null) return;

        if (depth == res.size()){
            res.add(root.val);
        }
        
        traverse(root.right, depth + 1);
        traverse(root.left, depth + 1);
    }
}

 

시간복잡도

모든 노드를 방문하고 있습니다.

O(n)의 시간복잡도가 필요합니다.

 

느낀점

문제 해결을 위한 아이디어를 떠올리는것이 너무 어려웠습니다.

다양한 방법으로 빠르게 접근하는 연습을 해야겠습니다.

 

참고

Beats 100% (DFS using recursion) - Binary Tree Right Side View - LeetCode