Construct Binary Tree from Inorder and Postorder Traversal

---

💬 문제

[문제 링크]

어떤 트리의 후위 순회로 읽었을 때의 값 배열 postorder
중위 순회로 읽었을 때의 값 배열 inorder
두 배열을 참고하여 트리를 생성한 후 root 노드 반환

✍️ 나의 풀이

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    if (postorder.length === 0)
        return null;

    let root = postorder.pop();
    let res = new TreeNode(root, null, null);
    let idx = inorder.indexOf(root);

    res.left = buildTree(inorder.slice(0, idx), postorder.slice(0, idx));
    res.right = buildTree(inorder.slice(idx + 1), postorder.slice(idx));

    return res;
};

Preorder + Inorder 문제와 똑같은 방식으로 진행
다른 점은 root 노드 선정을 postorder의 마지막 값으로 함

📌 결과

Accepted
Runtime 133ms (Beats 34.97%)
Memory 127.58MB (Beats 15.62%)

📚 러닝 포인트

후위 순회(Preorder)는 Left-Right-Root로 진행된다. 전위 순회와 유일하게 다른 점이 Root의 위치이므로 shift로 맨 앞 노드를 꺼내줬던 것을 pop을 통해 뒤에서 꺼내면 완성이다. 이전 문제를 풀면서 순회 방법에 대해 익히고 나니 이번 문제는 푼 것 같지도 않은 느낌으로 끝났다. 그래서 성능을 올려보려고 했다. 이전 문제의 솔루션을 구경했을 때, 배열 탐색 문제를 해결하기 위해 map으로 사용했던 사람도 있었고 slice 대신 인덱스 값으로 인자를 넘겨 속도를 올린 사람도 있었다. 나는 둘 중 인덱스 값 사용을 선택했다.

var buildTree = function(inorder, postorder) {
    var repeat = function(inStart, inEnd, postStart, postEnd) {
        if (postStart > postEnd)
            return null;

        let root = postorder[postEnd];
        let res = new TreeNode(root, null, null);
        let idx = inorder.indexOf(root);

        res.left = repeat(inStart, idx - 1, postStart, postStart + (idx - 1 - inStart));
        res.right = repeat(idx + 1, inEnd, postStart + idx - inStart, postEnd - 1);

        return res;
    }   
    return repeat(0, inorder.length - 1, 0, postorder.length - 1);
};

slice한 부분 배열처럼 보이기 위해 각 배열의 start, end 인덱스를 넘겨준다. 이 때 인덱스 값을 정하는 부분이 조금 헷갈릴 수 있는데, 저번부터 가장 중요한 포인트는 다음 중위 순회 배열의 크기만큼 후위 순위 배열의 크기를 정하는 것이다. 서브 노드 트리의 개수는 두 배열에서 같은 것이므로! 또한 중위 순회도 left-right이고 후위 순회도 left-right이기 때문에 중위 순회의 왼편 개수만큼 후위 순회의 앞에서부터 묶고, 중위 순회의 오른편 개수만큼 후위 순회의 뒤쪽을 묶으면 된다. idx - 1 - inStart이 중위 순회의 앞 묶음 노드 개수니까 postStart, 즉 후위 순회 배열의 맨 앞에서부터 저만큼까지를 범위로 지정한다. 오른편은 idx - inStart가 왼편 노드 개수이므로 postStart에 해당 값을 더한 곳부터 오른편 범위로 지정한다.

이렇게 제출했을 때 결과가 무려... 66ms / 54.32MB가 나왔다! 여전히 배열 인덱스로 참조하는 코드와 indexOf 함수가 있음에도 불구하고 slice를 대체한 것만으로도 이만큼의 성능 증가를 확인할 수 있었다.