[백준2263_자바스크립트(javascript)] - 트리의 순회

🔴 문제

트리의 순회

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], inOrder, postOrder] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const inOrderMap = new Map();
const ans = [];

for (let i = 0; i < n; i++) {
  inOrderMap.set(inOrder[i], i);
}

const getPostOrderTree = (inStart, inEnd, postStart, postEnd) => {
  if (inStart > inEnd || postStart > postEnd) return;
  const root = postOrder[postEnd];
  ans.push(root);

  const rootIdx = inOrderMap.get(root);

  const leftTreeSize = rootIdx - inStart;

  getPostOrderTree(inStart, rootIdx - 1, postStart, postStart + leftTreeSize - 1);
  getPostOrderTree(rootIdx + 1, inEnd, postStart + leftTreeSize, postEnd - 1);
};

getPostOrderTree(0, n - 1, 0, n - 1);

console.log(ans.join(' ').trim());

🟢 풀이

⏰ 소요한 시간 : -

이 문제는 중위순회와 후위순회 결과를 통해 전위순회를 구하는 문제다.

• 후위 순회의 마지막 요소는 항상 현재 서브트리의 루트 노드다.
• 중위 순회에서는 루트를 기준으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리다.

이 두 개념을 기반으로 전위 순회를 찾아내면 된다.

getPostOrderTree함수는 4개의 매개변수를 가진다.
isStart, isEnd는 현재 서브트리의 중위순회 범위고, postStart와 postEnd는 현재 서브트리의 후위순회 범위이다.

처음에는 트리 전체를 대상으로 하기 때문에 각각 0,n-1로 시작하여 재귀적으로 탐색한다.

이 때 inStart가 inEnd보다 크다거나, postStart가 postEnd보다 커서 트리 범위가 이상해진 경우 재귀탐색을 종료한다.

탐색 범위가 올바르다면, 후위순회의 마지막 요소 postOrder[postEnd]는 현재 서브트리의 루트이므로 전위 순회 결과인 ans에 가장 먼저 추가한다.
그 후 중위 순회에서는 루트를 기준으로 왼쪽/오른쪽 서브트리로 나눈 뒤 각자의 범위를 계산해서 getPostOrderTree함수를 재귀호출하면 된다.

🔵 Ref