js實(shí)現(xiàn)重建二叉樹(shù)的算法解析

/* 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;
}