전위순회 트리결과를 후위순회 트리결과로 출력하는 문제

트리설명: 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다
전위 순회: rootNode -> leftNode -> rightNode
후위순회: leftNode -> rightNode -> rootNode

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

const tree = input.map(Number);

let postOrder = [];

function getPostOrder(start, end) {
  if (start > end) return;
  const root = tree[start];

  // 오른쪽 자식이 시작하는 인덱스 기억하기
  let rightIdx = start + 1;

  // root보다 커지는 시점이 오른쪽 자식 시작 인덱스
  while (rightIdx <= end) {
    if (tree[rightIdx] > root) {
      break;
    }
    rightIdx++;
  }

  getPostOrder(start + 1, rightIdx - 1);
  getPostOrder(rightIdx, end);

  postOrder.push(root);
}

getPostOrder(0, tree.length - 1);
console.log(postOrder.join("\n"));

실행 순서 시뮬레이션

전위 순회 결과가 [50, 30, 80]인 트리

1. getPostOrder(0, 2) 호출: 루트는 50입니다.
2. 왼쪽 재귀 호출: getPostOrder(1, 1) (값: 30)이 먼저 실행
   • 30은 자식이 없으므로 바로 result.push(30)을 수행하고 종료 (결과: [30])
3. 오른쪽 재귀 호출: 다시 50으로 돌아와서 getPostOrder(2, 2) (값: 80)가 실행됩니다.
   • 80도 자식이 없으므로 result.push(80)을 수행하고 종료(결과: [30, 80])
4. 마지막 단계: 양쪽 자식 호출이 모두 끝났으니, 이제 getPostOrder(0, 2)의 마지막 줄인 result.push(50)이 실행 (최종 결과: [30, 80, 50])

결국 코드 상에서 push를 마지막에 적었기 때문에, 실제 배열에는 왼쪽 끝에 있는 잎새 노드(Leaf Node)부터 차곡차곡 쌓이게 되는 것