이진트리 후위 순회

const levelOrderTraversal = (root) => {
  const result = []; // 결과를 저장할 배열
  if (!root) return result; // 빈 트리일 경우 빈 배열 반환

  const queue = [root]; // 큐를 초기화하고 루트 노드를 삽입
  //queue라는 배열을 생성하고, 이진 트리의 루트 노드를 queue 배열에 넣는다.
  

  while (queue.length > 0) {
    const currentLevelSize = queue.length; // 현재 레벨의 크기 저장
    const currentLevel = []; // 현재 레벨의 노드를 저장할 배열

    for (let i = 0; i < currentLevelSize; i++) {
      const node = queue.shift(); // 큐에서 노드를 추출
      currentLevel.push(node.val); // 현재 레벨 배열에 노드 값 추가

      // 노드의 자식 노드를 큐에 삽입
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

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

  return result; // 결과 배열 반환
};

예시

       1
     /   \
    2     3
   / \     \
  4   5     6​

result라는 배열을 초기화

result 배열이 초기화되었다면, 큐를 생성

queueu = [1]

 

큐의 길이가 0이 될 때까지 반복문을 실행

큐의 길이가 0이 되면, 모든 레벨의 노드를 방문했기 때문에 결과 배열 result를 반환

 

큐의 길이가 0이 아니라면, 현재 레벨의 노드를 추출하기 위해 현재 레벨의 크기를 저장

이는 나중에 현재 레벨의 노드를 추출할 때 사용

 

현재 레벨의 배열 currentLevel도 초기화

큐에서 현재 레벨의 노드를 추출

큐에서 1을 추출

 

그 다음으로 추출된 노드의 자식 노드를 큐에 추가합

트리에서는 1의 자식 노드인 2와 3을 큐에 추가합니다. 따라서 큐는 [2, 3] 가 된다.

 

두 번째 반복문이 실행

currentLevelSize는 2

큐에서 2와 3을 추출하여 currentLevel 배열에 추가

currentLevel 배열은 [2, 3]

 

2와 3의 자식 노드를 큐에 추가

2의 자식 노드인 4와 5를 큐에 추가하고, 3의 자식 노드인 6을 큐에 추가

따라서 큐는 [4, 5, 6] 이 된다.

 

currentLevelSize가 3이므로 큐에서 4, 5, 6을 추출하여 currentLevel 배열에 추가

 

result는 [[1],[2,3],[4,5,6]]가 된다.