7/13일 BFS 문제.

패스트캠퍼스에서 나동빈님 javascript 코딩테스트 강의를 들으면서 풀어볼 문제를찾았다.
(백준은 아무래도 아직 적응이 덜됐음..)

codewars 테스트 코드에서 주어진 binary tree class가 적용이 되어 문제 제출(사이트내에서)은 문제없지만,
따로 rootNode를 만들어서 vscode에서 실행해봤다.

const rootNode = {
  value: 2,
  left: {
    value: 8,
    left: {
      value: 1,
      left: null,
      right: null
    },
    right: {
      value: 3,
      left: null,
      right: null
    }
  },
  right: {
    value: 9,
    left: {
      value: 4,
      left: null,
      right: null
    },
    right: {
      value: 5,
      left: null,
      right: null
    }
  }
};

트리구조 그린사이트

이렇게 되면, 어떤식의 트리구조가 나오느냐.

이렇게 나온다.
문제가 요구하는 건 BFS 즉 너비 우선 탐색이므로

이렇게 [2,8,9,1,3,4,5] 나와야한다.

function treeByLevels (rootNode) {
  if (rootNode === null) {
    return [];
  }

  const queue = [];
  const result = [];

  queue.push(rootNode);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node.value);

    if (node.left !== null) {
      queue.push(node.left);
    }
    if (node.right !== null) {
      queue.push(node.right);
    }
  }

  return result;
}

rootNode가 null이면 빈배열을 반환하고,
queue와 result를 빈배열로,
while문을 돌면서 queue가 빈배열이 될떄까지 조건을 걸어준다.