[ Top Interview 150 ] 199. Binary Tree Right Side View

문제

199. Binary Tree Right Side View

 Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

• Input : 이진 트리의 root 노드
• Output : 각 계층별 가장 오른쪽에 있는 노드들의 값의 Array
  • top 에서부터 bottom 으로 Array를 구성

알고리즘 전략

• 전략 1. 재귀적 방법

  • 기본 전략
    • Tree 구조 자체가 재귀적인 형태를 취함 (하위 node를 보아도 Tree 구조로 이루어짐)
    • 하위 정보를 이용하여 상위 정보를 만들 수 있음
    • Time complexity : $O(nlogn)$
  • 알고리즘 전략
    • 오른쪽 노드의 rightSideView와 왼쪽 노드의 rightSideView를 가져옴
    • (root node - 오른쪽 노드의 rightSideView - 왼쪽 노드의 rightSideView 일부)를 반환함
      • 왼쪽 노드의 rightSideView 일부 : 오른쪽 노드의 rightSideView보다 길 때, 긴 만큼의 뒷부분만을 넣음

• 전략 2. Queue를 이용

  • 기본 전략
    • 637. Average of Levels in Binary Tree의 모범 답안에서 Queue를 이용한 방법을 차용함
    • Tree 구조에서 계층별 데이터가 필요할 때 Queue를 이용하는 것이 매유 용이함
    • Time complexity : $O(n)$
  • 알고리즘 전략
    • Queue를 만들고 root 노드를 넣음
    • Queue가 비어있을 때까지 반복
      • Queue 가장 앞에 있는 노드의 값을 rightValues에 넣음
      • Queue에 있는 노드들의 하위 노드를 다시 Queue에 넣고, 상위 노드들은 다 제거함

답안 1 (재귀적 방법)

• Time complexity : $O(nlogn)$

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return List.of();
        }

        List<Integer> left = rightSideView(root.left);
        List<Integer> right = rightSideView(root.right);

        List<Integer> answer = new ArrayList<>();        
        answer.add(root.val);
        answer.addAll(right);
        for (int i = right.size(); i < left.size(); i++) {
            answer.add(left.get(i));
        }

        return answer;
    }
}

답안 2 (Queue를 이용)

• Time complexity : $O(n)$

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return List.of();
        }

        List<Integer> rightValues = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (queue.size() > 0) {
            int count = queue.size();
            
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                if (i == 0) { rightValues.add(node.val); }
                if (node.right != null) { queue.add(node.right); }
                if (node.left != null) { queue.add(node.left); }
            }
        }

        return rightValues;
    }
}