「剣指offer」――JavaScript(4)二叉樹の再建

二叉の木を再建する
テーマの説明
二叉の木の前の順序と中の順序が巡回した結果を入力して、二叉の木を再構築してください.入力された前の順序と中の順序を巡回した結果には重複した数字が含まれていないと仮定します.例えば、シーケンス｛1,2,4,7,3,5,6,8｝と中順序巡回シーケンス｛4,7,2,1,5,3,8,6｝を入力すると、二叉ツリーを再構築して戻ります.
コードを実現

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    // write code here
    if (!pre || pre.length === 0) {
        return;
    }
    var treeNode = {
        val: pre[0]
    }
    for(var i = 0; i < pre.length; i++) {
        if (vin[i] === pre[0]) {
            treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));
            treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));
        }
    }
    return treeNode;
    console.log(treeNode)
}

関連知識
二叉樹は、各ノードが最大で2つのサブツリーを持つツリー構造である.最初にルートを訪問して、左のツリーを巡回して、最後に右のツリーを巡回します.中順に左の木を遍歴して、もう一度根を尋ねます.最後に中順に右の木を遍歴します.後端を巡回します.まず、左の木を巡回して、右の木を巡回して、最後にルートを訪問します.
考え方
まず、最初の位置を巡回するのはルートノードtreeNodeで、中間pのルートノード位置を巡回し、pの左側には必ずtreeNodeの左サブツリーの中から順に配列され、pの右側にはtreeNodeの右サブツリーの中から配列されているに違いない.一方、先に遍歴した第二の位置からpまで、またtreeNode左の子樹の順のサブアレイであり、pの右に残っているのがtreeeNodeの右の子樹の順のサブアレイであり、4つの配列を探し出し、左右再帰的に呼び出せば良い.