[leetcode] 199. Binary Tree Right Side View(Java, BFS)

leetcode.com/problems/binary-tree-right-side-view/

Binary Tree Right Side View - LeetCode

 

## 접근방법

---

처음에 문제를 해석하다가, Right Side라고 해서 트리노드의 오른쪽 노드들을 출력하는줄 알았다 ㅠ...

 

 

하지만 그게 아니라, 트리를 오른쪽에서 바라봤을때 보이는 노드들을 출력하는 것이다. 즉, 같은 레벨에서 가장 오른쪽에 있는 노드들을 출력하면 된다.

 

 

우선 트리의 노드들을 모두 방문할 필요가 있다. 레벨을 순차적으로 방문하기 좋은 알고리즘은 BFS 알고리즘이다. 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> result = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        
        q.add(root);
 
        while(!q.isEmpty()){
            int val = 0;
            int sz = q.size();
            
            for(int i = 0; i < sz; i++){
                TreeNode cur = q.poll();
                if(cur == null) break;
                
                if(i == sz - 1) result.add(cur.val);
                
                if(cur.left != null) q.add(cur.left);
                if(cur.right != null) q.add(cur.right);
            }
        }
        
        return result;
    }
}