아이디어 스케치

1 3 4 5 6     7.      12 15 16
1 4 6 5 3.    12 16 15       7

1    3     4 5 6
1    4 6 5     3

preorder출력하기

  루트노드(A)
  루트노드의 왼쪽 자식 탐색(B)
    루트노드(A)
    왼쪽 자식이 한개 남은 경우(B)
    오른쪽 자식 탐색(C)
    (A-B)반복

왼쪽 자식이 한 개 나을 때까지
루트 노드를 preorder에 넣고
루트노드의 왼쪽 자식 탐색하고
루트 노드를 preorder에 넣고
루트 노드의 왼쪽 자식 탐색  .... 반복
왼쪽 자식 한개 남은경우: 왼쪽 자식 프리오더에 넣기

실패코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const n = input[0];
const inorder = input[1].split(" ").map(Number);
const postorder = input[2].split(" ").map(Number);

let preorder = [];

let rightChildsInorderQueue = [];
let rightChildsPostorderQueue = [];

function FindRootNode(partOfPostorder) {
  const rootNode = partOfPostorder[partOfPostorder.length - 1];
  preorder.push(rootNode);
  return rootNode;
}

function FindLeftNode(partOfInorder, partOfPostorder) {
  if (partOfInorder.length === 0) return;

  let rootNode = FindRootNode(partOfPostorder);
  const rootIndex = partOfInorder.indexOf(rootNode);

  const leftChildsIn = partOfInorder.slice(0, rootIndex);
  const leftChildsPost = partOfPostorder.slice(0, leftChildsIn.length);

  const rightChildsIn = inorder.slice(rootIndex + 1);
  const rightChildsPost = partOfPostorder.slice(
    leftChildsIn.length,
    partOfPostorder.length - 1,
  );

  if (rightChildsIn.length > 0) {
    rightChildsInorderQueue.push(rightChildsIn);
    rightChildsPostorderQueue.push(rightChildsPost);
  }

  if (leftChildsIn.length > 0) {
    FindLeftNode(leftChildsIn, leftChildsPost);
  }
}

FindLeftNode(inorder, postorder);

// FindLeftNode돌려서 주어진 그래프의 오른쪽 자식들 rightNodesQueue에 넣음
while (rightChildsInorderQueue.length > 0) {
  let nextIn = rightChildsInorderQueue.pop();
  let nextPost = rightChildsPostorderQueue.pop();
  FindLeftNode(nextIn, nextPost);
}

console.log(preorder);

메모리 초과를 피하려면 배열을 자르지 말고, 배열의 시작 인덱스와 끝 인덱스만 전달해야함

또한 indexOf 대신 루트의 위치를 미리 저장한 position 배열을 사용하면 탐색 속도가 $O(1)$로 빨라집니다.

성공코드

const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const n = input[0];
const inorder = input[1].split(" ").map(Number);
const postorder = input[2].split(" ").map(Number);

let preorder = [];

const position = new Array(n + 1);
for (let i = 0; i < n; i++) {
  position[inorder[i]] = i;
}

function solve(inStart, inEnd, postStart, postEnd) {
  if (inStart > inEnd || postStart > postEnd) return;

  // 1. Root 찾기 (Postorder의 끝)
  const rootNode = postorder[postEnd];
  preorder.push(rootNode);

  // 2. Inorder에서 Root의 위치 (미리 만든 position 배열 사용)
  const rootIndex = position[rootNode];

  // 3. 왼쪽 서브트리의 크기 계산
  const leftSize = rootIndex - inStart;

  // 4. 왼쪽 서브트리 방문
  solve(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);

  // 5. 오른쪽 서브트리 방문
  solve(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
}

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

console.log(preorder.join(" "));