這篇文章要跟大家介紹的內容是關於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實作重建二元樹的演算法解析的詳細內容。更多資訊請關注PHP中文網其他相關文章！
