문제 링크

문제 설명

입력으로 노드의 수, 트리 연결 관계를 받아서

• 전위 순회
• 중위 순회
• 후위 순회

위의 3가지 방식으로 순회를 했을 때의 결과를 출력하는 문제이다.

풀이 과정

• 전위 순회 : 루트(root) 노드부터 시작하여 방문
• 중위 순회 : 왼쪽 하위부터 루트(root)로 방문
• 후위 순회 : 하위 트리 모두 방문 후 루트(root) 방문

우선 트리를 객체로 저장하여 노드이름 - [왼쪽 자식, 오른쪽 자식]으로 저장한다.

트리 저장

    const N = Number(input.shift());
    const tree = {};

    for (let i = 0; i < N; i++) {
        const [node, left, right] = input[i].split(" ");
        tree[node] = [left, right];
    }

전체 코드와 설명

    let fs = require("fs");
    let input = fs.readFileSync("./input.text").toString().trim().split("\n");
    const N = Number(input.shift());
    let result = '';
	// 트리 저장
    const tree = {};
    for (let i = 0; i < N; i++) {
        const [node, left, right] = input[i].split(" ");
        tree[node] = [left, right];
    }
	//전위 순회 
    function pre(node) {
	    // 자식이 없을 경우 종료
        if (node === '.'){
            return;
        }
        const [left, right] = tree[node];
        //루트 노드부터 저장
        result += node;
      	//왼쪽 자식 노드 저장
        pre(left);
      	//오른쪽 자식 노드 저장
        pre(right);
    }

	//중위 순회
    function mid(node) {
        if (node === '.'){
            return;
        }
        const [left, right] = tree[node];
		// 재귀를 통해 왼쪽 가장 밑에 있는 자식 노드 저장
        mid(left);
      	// 왼쪽 자식 저장 후 부모 노드 저장
        result += node;
      	// 오른쪽 자식 저장
        mid(right);
    }

	//후위 순회
    function post(node) {
        if (node === '.'){
            return;
        }
        const [left, right] = tree[node];
      	//자식 노드 전부 방문 후 부모 노드로 방문
        post(left);
        post(right);
        result += node;
    }
    pre('A');
    result += '\n';
    mid('A');
    result += '\n'
    post('A');
    result += '\n';
    console.log(result)

}

후기

트리 순회에 대해 다시 한번 공부할 수 있는 문제였다.