240808

문제 : 길 찾기 게임 난이도 : Lv.3

풀이

function solution(nodeinfo) {
    // 노드 정보에 index를 추가 (노드 번호 저장)
    nodeinfo = nodeinfo.map((node, index) => [...node, index + 1]);

    // y 좌표 기준 내림차순, x 좌표 기준 오름차순으로 정렬
    nodeinfo.sort((a, b) => b[1] - a[1] || a[0] - b[0]);

    // 이진 트리를 구성하는 함수
    function insertNode(parent, child) {
        if (child[0] < parent[0]) {
            if (parent.left === null) {
                parent.left = child;
            } else {
                insertNode(parent.left, child);
            }
        } else {
            if (parent.right === null) {
                parent.right = child;
            } else {
                insertNode(parent.right, child);
            }
        }
    }

    // 트리 구조 생성
    let root = nodeinfo[0];
    root.left = null;
    root.right = null;

    for (let i = 1; i < nodeinfo.length; i++) {
        nodeinfo[i].left = null;
        nodeinfo[i].right = null;
        insertNode(root, nodeinfo[i]);
    }

    // 전위 순회 (Preorder)
    let preorder = [];
    function preorderTraversal(node) {
        if (node) {
            preorder.push(node[2]);
            preorderTraversal(node.left);
            preorderTraversal(node.right);
        }
    }
    preorderTraversal(root);

    // 후위 순회 (Postorder)
    let postorder = [];
    function postorderTraversal(node) {
        if (node) {
            postorderTraversal(node.left);
            postorderTraversal(node.right);
            postorder.push(node[2]);
        }
    }
    postorderTraversal(root);

    return [preorder, postorder];
}