js實作重建二元樹的演算法解析

這篇文章要跟大家介紹的內容是關於js實作重建二元樹的演算法解析，有著一定的參考價值，有需要的朋友可以參考一下。

題目描述

輸入某二元樹的前序遍歷和中序遍歷的結果，請重建出該二元樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重複的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}及中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二元樹並返回。

分析

前序遍歷是中左右的順序，中序遍歷是左中右的順序，那麼對於{1,2,4,7,3,5,6,8 }和{4,7,2,1,5,3,8,6}來說，1是根節點，然後1把中序遍歷的序列分割為兩部分，「4，7，2」為1的左子樹上的節點，「5，3，8，6」為1的右子樹上的節點，這樣遞歸的分解下去即可

程式碼實作

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    var root = recon(0, pre.length-1, pre, 0, vin.length-1, vin);
    return root;
}

function recon(preStart, preEnd, pre, vinStart, vinEnd, vin){
    if(preStart > preEnd || vinStart > vinEnd) {
        return null;
    }

    var node = new TreeNode(pre[preStart]);

    for(var i = vinStart;i <= vinEnd;i++) {
        if(vin[i] === pre[preStart]){
            node.left = recon(preStart+1, preStart+i-vinStart, pre, vinStart, i-1, vin);
            node.right = recon(preStart+i-vinStart+1, preEnd, pre, i+1, vinEnd, vin);
        }
    }

    return node;
}

相關推薦：

js中字串的全排列的演算法解析

#js如何實作將上傳圖片並且壓縮的方法

#

以上是js實作重建二元樹的演算法解析的詳細內容。更多資訊請關注PHP中文網其他相關文章！