[3주차] 199. Binary Tree Right Side View

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

Binary Tree Right Side View - LeetCode

---

📝 문제

리진트리의 루트가 주어진다. 해당 트리의 오른편에 있는 원소만 리스트에 담아서 리턴하시오.

 

 

🎈 풀이

트리의 각 레벨에서 가장 오른쪽에 원소를 담아 리턴하는 문제이다.

예를 들어,

 

 

위와 같은 트리에서 결과는 [10, 14, 9] 이다.

Queue 를 두 개 사용하여 해결하였다.

 

시간복잡도: O(n)

공간복잡도: O(n)

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

    public List<Integer> rightSideView(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return res;

        queue.offer(root);
        while (!queue.isEmpty()) {
            Queue<TreeNode> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                temp.offer(queue.poll());
            }

            res.add(temp.peek().val);

            while (!temp.isEmpty()) {
                TreeNode parent = temp.poll();
                if (parent.right != null) queue.add(parent.right);
                if (parent.left != null) queue.add(parent.left);
            }
        }

        return res;
    }

}

• 10~13행: 현재 queue 에 담겨있는 노드를 temp에 전부 옮긴다.
• 15행: temp 에서 다음 노드의 값이 가장 오른쪽에 있는 값이다. 이것을 만족하기 위해서는 오른쪽 자식 노드부터 queue 에 넣어야 한다.
• 17~21행: temp 에 있는 노드들의 자식을 전부 queue 에 넣는다.

 

이 방식을 사용하면 queue 에는 동일 레벨의 노드만이 담기게 된다. 또한, queue 에는 가장 오른쪽 자식부터 담기 때문에 queue의 첫 번째로 poll 될 노드의 집합이 결과가 된다.

 

📈 타 솔루션 참고

시간복잡도: O(n)

공간복잡도: O(n)

class Solution {
    int maxlevel = 0;
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list  = new ArrayList<>();
        right(root,1,list);
        return list ;
    }
    void right(TreeNode root,int level,List<Integer> list){
        if(root==null){
            return ;
        }
        if(maxlevel<level){
            list.add(root.val);
            maxlevel=level;
        }
        right(root.right,level+1,list);
        right(root.left,level+1,list);
        
    }
}

공간복잡도는 동일하나 메모리를 조금 더 아끼고, 로직 자체가 단순화된 모습이다.

레벨을 체크하기 위해 재귀함수의 파라미터에 int형 변수 level을 추가하였다. 또한, 전역변수로 maxLevel을 선언하였다.

재귀함수의 depth 가 올라갈 수록 level 또한 높아지고, 가장 처음 level이 현재 maxLevel과 달라지면 결과 list 에 값을 추가한다.

오른쪽 자식 노드부터 재귀를 들어가기 때문에 이와 같은 결과를 도출할 수 있다.