作者:wangyongjieyexuying677 | 来源:互联网 | 2024-11-04 12:30
本文深入探讨了基于前序遍历和中序遍历结果重构二叉树的算法。假设输入的前序遍历和中序遍历序列中均无重复数字,通过具体示例如前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列,详细解析了如何逐步重建原始二叉树结构。文章不仅提供了理论分析,还结合实际代码实现,帮助读者全面理解该算法的核心原理和应用方法。
问题形貌
输入某二叉树的前序遍历和中序遍历的效果,请重修出该二叉树。假定输入的前序遍历和中序遍历的效果中都不含反复的数字。比方输入前序遍历序列{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;
}