참고
문제해설
NOTE
•
입력 값 ⇒ TreeNode
•
출력 값 ⇒ BST의 오른쪽을 위에서 아래로 정렬된 값을 반환
문제 로직고민
NOTE
1.
처음 문제를 봤을때 그냥 오른쪽값만 쭉 반환하면 되는게 아닌가라고 생각했다.
반례 1
•
그런테 위와같은 경우에는 오른쪽만 보면 [1]이지만, 결과값이 [1,2]다.
•
즉 오른쪽에서 봤을때, 정렬하는 경우를 구해야한다.
2.
동일 레벨에서 가장 우측에 있는 값을 뱉어내야 한다.
•
레벨 1 탐색, 레벨 2탐색의 흐름을 그려보니 BFS방식이 생각났다.
•
BFS방식에서 동일한 레벨에서 가장 마지막에 탐색된 값을 넣으면된다!
•
BFS의 Queue<TreeNode>에서 level정보는 Queue<Integer>를 하나 더 생성한다.
•
동일한 레벨 체크는 배열로 진행한다, 크기는 노드의 수가 100개 이하이므로 101로 잡는다. (1부터 시작하기 위해서)
•
val의 범위가 최소 -100이므로, 모든 배열의 값을 -101로 초기화한다.
작성코드
NOTE
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList();
if(root == null) return result;
Queue<TreeNode> treeQueue = new LinkedList();
Queue<Integer> levelQueue = new LinkedList();
int[] valArray = new int[101];
for(int i=0; i<valArray.length; i++){
valArray[i] = -101;
}
treeQueue.add(root);
levelQueue.add(1);
while(!treeQueue.isEmpty() && !levelQueue.isEmpty()){
TreeNode node = treeQueue.poll();
int level = levelQueue.poll();
System.out.println(level);
valArray[level] = node.val;
if(node.left != null) {
treeQueue.add(node.left);
levelQueue.add(level+1);
}
if(node.right != null) {
treeQueue.add(node.right);
levelQueue.add(level+1);
}
}
for(int v : valArray){
if(v != -101) result.add(v);
}
return result;
}
}
Java
복사
정답코드
NOTE
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ans = new LinkedList<>();
rightview(root, ans, 0);
return ans;
}
public void rightview(TreeNode root, List<Integer> ans, int currDepth){
if(root ==null){
return ;
}
int size = ans.size();
if(size == currDepth){
ans.add(root.val);
}
rightview(root.right, ans, currDepth+1);
rightview(root.left, ans, currDepth+1);
}
}
Java
복사
시간이 가장 빠른 코드
•
메모리면에서는 좋게나와서 시간이 좋은 코드를 참고했다.
•
BFS가 아닌 DFS방식이며 나보다 더 효율적으로 동일 레벨의 가장 우측값을 찾았다.
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if(i == size - 1) {
res.add(cur.val);
}
if(cur.left != null) {
queue.add(cur.left);
}
if(cur.right != null) {
queue.add(cur.right);
}
}
}
return res;
}
}
Java
복사
시간이 빠른 코드
•
BFS방식으로도 내가 진행한 방식보다 훨씬 좋게 진행이 가능했다.
•
queue의 size를 사용한 방식으로, 동일 레벨에서 가장 우측값을 뽑아냈다.
◦
동일 레벨에서 가장 우측값은, Queue가 이전 레벨에서 담은 크기의 가장 끝에 담겨있기 때문