5639번 - 이진 검색 트리

1️⃣ Postorder Traversal

 

✏️ 풀이 과정

전위 순회의 순서를 바로 후위 순회의 순서로 변환하는 방법이 있지만 여기서는 트리를 복원한 이후에 후위 순회를 진행했습니다.

 

후위 순회의 경우 dfs를 이용하여 left child 재귀, right child 재귀, print를 순서대로 호출해서 구현할 수 있습니다.

 

트리는 이진 검색 트리의 특징을 이용하여 항상 따로 저장해놓은 head에서 출발하여 작으면 왼쪽, 크면 오른쪽으로 향하다가 null인 곳에 추가하는 방법으로 복원할 수 있습니다.

 

⏱ 시간 복잡도

트리를 복원할 때 head에서부터 탐색이 이루어지기 때문에 최악의 경우(한 쪽으로 쏠린 경우) O(n^2)이 됩니다. 나머지 과정은 전부 O(n)이기 때문에 노드의 수가 10,000개 이하임을 감안하면 100,000,000정도의 계산으로 끝나는 것을 예측할 수 있습니다.

 

💻 코드

JavaScript

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

class Node {
    constructor(val, l, r) {
        this.val = val;
        this.l = l;
        this.r = l;
    }
}

let head = new Node(Number(input[0]), null, null);

const add = (val) => {
    let cur = head;
    while (true) {
        if (val < cur.val) {
            if (!cur.l) {
                cur.l = new Node(val, null, null);
                break;
            }
            cur = cur.l;
        } else {
            if (!cur.r) {
                cur.r = new Node(val, null, null);
                break;
            }
            cur = cur.r;
        }
    }
};

for (let i = 1; i < input.length; i++) {
    add(Number(input[i]));
}

const res = [];

const postOrder = (n) => {
    if (n.l) postOrder(n.l);
    if (n.r) postOrder(n.r);
    res.push(n.val);
};

postOrder(head);

console.log(res.join("\n"));