[LeetCode] 199. Binary Tree Right Side View - Java

Binary Tree Right Side View - LeetCode

 

문제

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

 

이진 트리의 root가 주어졌을 때, 자신이 그 오른쪽에 서 있다고 상상하고, 위에서 아래로 순서화된 노드의 값을 반환하는 문제이다.

 

---

 

내 풀이

 

처음에는 문제를 잘못 이해해서 트리의 오른쪽 노드들을 출력하는 문제인 줄 알았다.

간단하게 오른쪽 노드들만 탐색하는 코드를 작성했는데 틀려서 문제를 다시 보니,

트리의 오른쪽에서 바라봤을 때 보이는 노드들, 즉 각 레벨에서 가장 오른쪽에 있는 노드들을 출력하는 문제이다.

BFS를 사용해서 트리의 모든 노드를 탐색해야한다.

 

BFS 사용

/**
 * 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;
 *     }
 * }
 */
class Solution {

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> answer = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

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

        queue.offer(root);

        while(!queue.isEmpty()){
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                if (i == size - 1) {
                    answer.add(node.val);
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return answer;
    }
}

 

큐를 사용하여 BFS를 구현했다.

각 레벨마다 for문을 돌며 그 레벨의 마지막 노드(가장 오른쪽 노드)를 리스트에 추가하는 로직이다.

 

• 시간복잡도 : O(N) - 모든 노드 순회
• 공간복잡도 : O(W)
  • 큐의 크기에 따라 공간복잡도가 결정된다.
  • 큐의 최대 크기는 트리의 가장 넓은 레벨의 노드의 수(W) 이다.

 

---

 

다른 사람의 풀이

 

DFS 사용

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);
    }
}

right 메서드가 루트노드의 오른쪽 노드부터 DFS를 수행하며 각 레벨에서 오른쪽에서 처음 방문하는 노드의 값을 리스트에 추가한다.

 

• 시간복잡도 : O(N)
• 공간복잡도 : O(log N)