[코플릿] 이진트리 레벨순회(levelorder)

문제

이진트리의 root노드를 줄 것입니다. 해당 이진트리의 레벨 순회 결과를 출력하세요.

입력

인자 1 : TreeNode

• TreeNode 타입으로 된 root 노드

출력

• number[][] 을 리턴해야 합니다.

주의 사항

• 이진트리 내의 노드 갯수의 범위는 0 - 2000 입니다.

입출력 예시

class TreeNode {
	constructor(val, left, right) {
		this.val = val === undefined ? 0 : val;
		this.left = left === undefined ? null : left;
		this.right = right === undefined ? null : right;
	}
}


/*
        3
       / \
      9  20
        /  \
       15   7
*/
const root1 = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
const result1 = levelOrderTraversal(root1);
console.log(result1); // [[3], [9, 20], [15, 7]];

const root2 = new TreeNode(1);
const result2 = levelOrderTraversal(root2);
console.log(result2); // [[1]]

const root3 = null;
const result3 = levelOrderTraversal(root3);
console.log(result3); // []

 

 

 

풀이

---

const levelOrderTraversal = (root) => {
  if (root === null) return []; // 빈 트리인 경우, 빈 배열 반환

  const result = []; // 순회 결과를 저장하기 위한 배열
  const queue = [root]; // 노드를 저장하기 위한 큐

  while (queue.length > 0) {
    const size = queue.length; // 현재 레벨의 노드 개수를 저장

    const group = []; // 현재 레벨의 노드 값을 저장하기 위한 배열

    for (let i = 0; i < size; i++) {
      const curr = queue.shift(); // 큐에서 노드를 꺼냄
      group.push(curr.val); // 현재 레벨의 노드 값을 배열에 추가

      if (curr.left) queue.push(curr.left); // 왼쪽 자식이 있으면 큐에 추가
      if (curr.right) queue.push(curr.right); // 오른쪽 자식이 있으면 큐에 추가
    }

    result.push(group); // 현재 레벨의 노드 값 배열을 결과 배열에 추가
  }

  return result; // 레벨 순서 순회 결과 반환
}

• 주어진 이진 트리의 루트 노드를 큐에 추가한 뒤, 큐가 비어질 때까지 반복합니다.
• 각 레벨별로 현재 큐에 있는 노드의 개수만큼 반복하면서 큐에서 노드를 꺼내고, 해당 노드의 값을 현재 레벨의 값 배열에 추가합니다.
• 그리고 해당 노드의 자식들을 큐에 추가하여 다음 레벨을 탐색합니다.
• 마지막으로 각 레벨의 값 배열을 결과 배열에 추가하고, 최종적으로 결과 배열을 반환합니다.