[LeetCode/Top Interview 150] [Binary Tree BFS (Breadth-First Search)] 199. Binary Tree Right Side View

문제 링크: https://leetcode.com/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

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.

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: []

Constraints:

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

전략:

전체 트리 중 같은 높이 중 가장 오른쪽에 있는 노드만 모아서 정렬하는 문제.

만약 같은 높이가 없다면, 가장 왼쪽에 있는 리프노드도 확인해야 할 것이다.	높이별로 트리의 정렬 순서가 보장되지 않을 수 있다.(상관 X)

우선은 효율보다는 확실한 해법을 우선하자.
Queue사용해서 BFS로 높이별로 순회하며 왼쪽 노드부터 삽입하며, 한 높이의 마지막 노드라면 정렬대상으로 ArrayList 추가
BFS 순회가 끝나면 정렬하여 출력(정렬할 필요는 없음)

코드 구현:

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> answer = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        int level_pushed = 1; // root 요소 1개

        if (root == null) { return answer; }

        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode now = q.poll();
            level_pushed--;

            if (now.left!=null) {
                q.offer(now.left);
            }
            if (now.right!=null) {
                q.offer(now.right);
            }
            if (level_pushed==0) { // 한 높이의 마지막 요소
                answer.add(now.val);
                // 높이 초기화
                level_pushed = q.size();
            }
        }
        return answer;
    }
}
Time: 1 ms (65.57%), Space: 40.66MB (98.37%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0199-binary-tree-right-side-view/0199-binary-tree-right-side-view.java

개선 방안:

BFS용 큐를 별도로 사용하지 않고 재귀로 변경해서 오른쪽부터 순회하며 풀기

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> answer = new ArrayList<Integer>();
        BFS(root, answer, 0);
        return answer;
    }

    public void BFS(TreeNode node, List<Integer> answer, int level) {
        if (node == null) { return; }

        if(answer.size() == level){
            answer.add(node.val);
        }

        BFS(node.right, answer, level+1);
        BFS(node.left, answer, level+1);
    }
}
Time: 0 ms (100.00%), Space: 40.63 MB (98.37%) - LeetHub

Solutions 탭의 타인 코드:

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        var list = new ArrayList<Integer>();
        rec(root,list,0);
        return list;
    }
    void rec(TreeNode root,ArrayList<Integer> list, int depth){
        if (root == null) return;
        if(list.size()==depth) list.add(root.val);
        if(root.right!=null) rec(root.right,list,depth+1);
        if(root.left!=null) rec(root.left,list,depth+1);
    }
}
Time: 0 ms (100%), Space: 41.06MB (74.82%) - LeetHub

회고:

처음에 문제를 잘못 이해해서 오른쪽 노드들을 모아서 정렬하는 과정이 필요할 줄 알았다.
확실히 같은 내용이면 재귀로 푸는 편이 코드도 짧고, 더 빠른 실행시간을 가지는 경우가 있는 것 같다. 하지만 재귀는 Stack Overflow의 주범이 될 수 있으니 그만큼 문제가 발생하지 않도록 로직을 잘 구현하는 것이 중요할 것이다.