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 <p>相關推薦：</p><p class="comments-box-content"><a href="http://www.php.cn/js-tutorial-406764.html" target="_blank" title="js中字符串的全排列的算法解析">js中字串的全排列的演算法解析</a><br></p><p class="mt20 ad-detail-mm hidden-xs"><a href="http://www.php.cn/js-tutorial-406767.html" target="_blank" title="js如何实现将上传图片并且压缩的方法">#js如何實作將上傳圖片並且壓縮的方法</a><br> </p>#

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