.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
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]
Java
복사
Example 2:
Input: root = [1,null,3]
Output: [1,3]
Java
복사
Example 3:
Input: root = []
Output: []
Java
복사
Constraints:
•
The number of nodes in the tree is in the range [0, 100].
•
100 <= Node.val <= 100
My solution
1
2 3
4 5 6 7
levelorder로 순회할 때의 인덱스와 같은 위치에 차례대로 들어가야함
const rightSideView = root => {
let rt = null;
const q = [];
function Node(value) {
this.left = null;
this.right = null;
this.key = value;
}
function insertValue(value) {
const node = new Node(value);
if (rt == null) rt = node;
else if (q[0].left == null) q[0].left = node;
else {
q[0].right = node;
q.shift();
}
q.push(node);
}
function createTree(arr, n) {
for (let i = 0; i < n; i++) insertValue(arr[i]);
}
createTree(root, root.length);
function levelOrder(root) {
if (root == null) return [];
const n = [];
n.push(root);
const answer = [];
while (n.length > 0) {
answer.push(n[0].key);
if (n[0].right != null) n.push(n[0].right);
n.shift();
}
return answer;
}
return levelOrder(rt);
};
JavaScript
복사
⇒ 테스트케이스 통과, 제출했을 때 다른 출력이 나옴
Level Order Traversal와 동일하게 큐를 통해
•
1) 루트 노드를 방문한다.
•
2) 루트 노드의 Left Child 를 방문한다.
•
3) 루트 노드의 Right Child를 방문한다.
while (queue.length) {
const n = queue.length;
for (let i = 0; i < n; i++) {
const temp = queue.shift();
if (i === n - 1) res.push(temp.val);
if (temp.left !== null) queue.push(temp.left);
if (temp.right !== null) queue.push(temp.right);
}
}
JavaScript
복사
[그림 3] 위의 이진 트리를 Level Order Traversal 할 것입니다.
다른 사람 풀이
소스코드
const rightSideView = root => {
if (root === null) {
return [];
}
const q = [root];
const answer = [];
while (q.length) {
const n = q.length
for(let i = 0; i<n; i++){
const temp = q.shift();
if (i === n - 1) answer.push(temp.val);
if (temp.left != null) q.push(temp.left);
if (temp.right != null) q.push(temp.right);
}
}
return answer;
};
JavaScript
복사
