从前序和中序的结果输出还原一颗二叉树

这个例子是在《数据结构》书本上看到的，大概看了一下思路，遂来实现一下。

前序遍历：先遍历根节点，再遍历左节点，最后遍历右节点中序遍历：先遍历左节点，再遍历中节点，最后遍历右节点

已知一颗二叉树的前序输出为：12485367
中序输出为：84251637

1、已知前序遍历顺序，得知1是根节点，我们把1拿到中序输出上，得到根节点的左节点输出和右节点输出：8425（左） 1 637（右）； 2、通过中序输出的左子树，推出前序输出的左子树和右子树 1 2485（左） 367（右）； 3、对前序和中序输出结果的字符串不断切割，重复第一步和第二步，最后还原整棵树；

下面是JavaScript的代码实现：

function restore(first,mid){
    let root = first[0];
    let tree = {
        value:root
    }
    for(let i =0;i<mid.length;i++){
        if(mid[i] === root){
            let left = mid.substring(0,i);
            let right = mid.substring(i+1);

            let fl = first.substring(1,left.length+1);
            let fr = first.substring(left.length+1);

            tree.left = restore(fl,left);
            tree.right = restore(fr,right);
        }
    }
    return tree;
}

zuluoaaa / blog

从前序和中序的结果输出还原一颗二叉树 #4