**🔗 참고 문제** → [<https://www.acmicpc.net/problem/5639>](<https://www.acmicpc.net/problem/5639>)      // 클릭 시 이동

# 📌 BST 전위 순회 -> 후위 순회 변환

이진 탐색 트리(Binary Search Tree)의 전위 순회 결과만 주어졌을 때, 실제 노드를 만들지 않고
배열 + 범위(Min, Max) + 전역 Idx 로 후위 순회를 바로 출력하는 방식

- 🔑 현재 값이 이 서브트리에 들어올 수 있는 범위인가 체크가 핵심 

🎯 문제 유형

• BST에서 순회 변환

🚮 선입견을 버리자

• 직접 Node를 만들어 사용하자 → ❌
  • 편향 트리일 시, 시간 초과 발생 가능
• 루트 기준으로 매번 왼쪽/오른쪽 구간을 선형 탐색해서 나누자 → ❌
  • O(N²) 이기 때문에 시간 초과 발생 가능
  • N 범위에 따라 가능한 경우도 존재 (참고 문제의 경우, 배열을 이용한 선형 탐색으로 풀이 가능)
• 트리를 생성해야 이후 작업이 가능하다 → ❌
  • BST의 범위 성질을 잘 이용하면 트리 생성 없이 후위 순회 등 가능

💭 어떻게 떠올릴까

• BST는 각 서브트리에 들어갈 수 있는 값의 범위가 정해져 있음
• 전위 순회는 루트 → 왼쪽 → 오른쪽 순서
  • 현재 보고 있는 값이 지금 서브트리의 허용 범위 안 → 이 서브트리의 루트로 사용 가능
  • 범위 밖 → 이 서브트리 값이 아님
• 따라서, 범위를 이용해서 현재 값이 어느 서브트리에 속하는지 판단 후 이를 재귀 처리 가능

🔑 핵심 원리

• pre[idx] 를 현재 볼 값이라고 가정

• 현재 서브트리가 허용하는 범위가 min ~ max 이면

  • min < pre[idx] < max → 현재 서브트리의 루트로 사용 가능 → 사용하고 idx 증가
  • 그 외 → 현재 서브트리 소속이 아님 → idx 그대로 두고 return

  🖐️ min, max 는 long 으로 두는 게 안전