문제
요구사항
- 이진 트리가 있다.
- 특정 노드의 왼쪽 서브트리의 모든 노드는 해당 노드보다 작다
- 특정 노드의 오른쪽 서브트리의 모든 노드는 해당 노드보다 크다.
- 전위 순회의 순서는 (루트)->(왼쪽 서브트리)->(오른쪽 서브트리) 이다.
- 후위 순회의 순서는 (왼쪽 서브트리)->(오른쪽 서브트리)->(루트)이다.
- 트리를 전위 순회로 방문했을 때의 노드의 순서가 입력값으로 주어진다. 입력값을 바탕으로 후위 순회한 결과를 출력해야한다.
코드
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n').map(Number);
const stack = [];
const result = [];
stack.push([0, input.length - 1]);
while (stack.length) {
const [start, end] = stack.pop();
if (start > end) continue;
result.push(input[start]); // 루트 노드
// 오른쪽 서브트리의 루트 구하기
const rightRoot = getRightRoot(start, end);
// 오른쪽 서브트리가 있을 경우
if (rightRoot) {
stack.push([start + 1, rightRoot - 1]); // 왼쪽 서브트리의 시작, 끝 인덱스
stack.push([rightRoot, end]); // 오른쪽 서브트리의 시작, 끝 인덱스
} else {
stack.push([start + 1, end]); // 루트 노드만 제거
}
}
console.log(result.reverse().join('\n'));
function getRightRoot(start, end) {
for (let i = start + 1; i <= end; i++) {
if (input[i] > input[start]) return i;
}
}풀이
전위 순회 탐색을 하면 (루트) -> (왼쪽 서브트리) -> (오른쪽 서브트리) 순서로 노드를 탐색한다.
따라서 다음과 같은 정보를 얻을 수 있다.
- 루트노드 A가 있다.
- A보다 '작은' 노드중 가장 먼저 나오는 노드 B는 A의 '왼쪽' 서브트리의 루트노드다.
- A보다 '큰' 노드중 가장 먼저 나오는 노드 C는 A의 '오른쪽' 서브트리의 루트노드다.
2, 3번 과정에서 B와 C를 루트노드로 설정하여 1번부터 재귀적으로 반복하면 전위 순회 방식으로 노드를 탐색할 수 있다.
재귀함수를 사용하면 더 코드가 간결해졌겠지만 Node.js에서는 기본적으로 콜스택의 최대 사이즈를 약 10000으로 설정하기 때문에 재귀함수를 사용하면 "런타임 에러(StackSizeExceeded)"가 나온다.
따라서 스택과 반복문을 이용해서 재귀를 구현한다. 루트 노드에 방문할 때마다 루트 노드를 result 배열에 푸시해주는 이유는 전위 순회에서는 (루트)를 처음으로 방문하지만 후위 순회에서는 (루트)를 마지막에 방문하므로 먼저 방문한 루트 노드를 result 배열의 아래쪽에 깔아둬야 출력 시 배열을 뒤집었을 때 올바른 후위 순회 순서로 출력되기 때문이다.
루트 노드는 stack의 top에 있는 서브트리에 의해 결정된다. 만약 stack의 top에 있는 서브트리가 오른쪽 서브트리라면 result 배열에도 오른쪽 서브트리의 루트 노드가 먼저 저장될 것이다. 반대로 top에 있는 서브트리가 왼쪽 서브트리라면 result 배열에도 왼쪽 서브트리의 루트 노드부터 저장될 것이다.
result 배열에는 다음과 같이 저장되어야 역순으로 출력했을 때 올바른 후위 순회 결과가 나온다.
result = [
(왼쪽 서브트리의 루트 노드),
(오른쪽 서브트리의 루트 노드),
(루트 노드)
]stack에 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 푸시하면 역순으로 오른쪽 서브트리 -> 왼쪽 서브트리 순으로 result 배열에 저장되므로 stack에는 왼쪽 서브트리부터 푸시해주는 것이다.
if(start > end) continue는 생략하면 start === end 일 때도 계속해서 스택에 원소를 추가하기 때문에 무한루프를 돌게 된다.
참고 블로그 : https://gywlsp.github.io/boj/5639/
