9/13 (수) BFS를 이용한 한 문제 풀이와 바뀐 LeetCode 레이아웃 TIL

공부한 것

• LeetCode #199. Binary Tree Right Side View

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

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

  

  => 주어진 이진 트리를 오른쪽으로 뉘여서 보았을 때 가장 윗면에 노출되는 노드를 root쪽부터 순서대로 배열에 담아서 반환하는 문제다. = 주어진 트리의 오른쪽 가장자리 노드들을 root부터 아래로 순서대로 배열에 담아서 반환하기. = 각 레벨의 가장 오른쪽 노드를 추출하기.

  1. 큐를 이용한 BFS(너비 우선 탐색)로 순회하여 풀었다:

     function rightSideView(root: TreeNode | null): number[] {
       // if given tree has 0 node, return empty array
       if (!root) return [];
     
     	const result: number[] = []; // result array to store right-most nodes of each level
     	const queue: Array<[TreeNode, number]> = [[root, 1]]; // queue for BFS iterating. store nodes together with its level in tree.
     	while (queue.length) {
     		const [node, level] = queue.shift();
     
             // check if this node is the last node of current level.
             // if it is, add this node to the result array.
     		const nextLevel = queue[0] ? queue[0][1] : null;
     		if (level !== nextLevel) result.push(node.val);
     
             // add child nodes to the queue
     		if (node.left) queue.push([node.left, level + 1]);
     		if (node.right) queue.push([node.right, level + 1]);
     	}
     
     	return result;
     };

P.S. 별 건 아니지만 LeetCode.com의 문제풀이 레이아웃이 바뀌었다. 일단 문제 타이틀이 더 크고 선명해진 게 마음에 든다. 핵심 변화는 Visual Studio Code 에서처럼 지문 창과 코드 작성 창, 결과 확인 창을 좀 더 자유롭게 축소, 분리 및 이동시킬 수 있게 됐다는 점이었다.

Uploaded by N2T