js 通过左右前序和中序， 或者后序和中序来还原二叉树

// 二叉树的生成
function NodeTree(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
// 通过二叉树的前序和中序来还原二叉树
let frontArr = ['a', 'c', 'f', 'g', 'b', 'd', 'e'];
let middleArr = ['f', 'c', 'g', 'a', 'd', 'b', 'e'];
let endArr = ['f', 'g', 'c', 'd', 'e', 'b', 'a'];
function restoreTreeByFrontAndMiddle(frontArr, middleArr) {
    // 逻辑判断
    if (!frontArr || frontArr.length === 0 || !middleArr || middleArr.length === 0 || frontArr === middleArr) return null;
    // 获取前序遍历的跟节点, 左子树的长度, 前序左子树，前序右子树， 中序左子树， 中序右子树
    let rootNode = new NodeTree(frontArr[0]), index = middleArr.indexOf(frontArr[0]),
        frontArrLeft = frontArr.slice(1, index + 1), frontArrRight = frontArr.slice(index + 1, frontArr.length),
        middleArrLeft = middleArr.slice(0, index), middleArrRight = middleArr.slice(index + 1, middleArr.length);
    rootNode.left = restoreTreeByFrontAndMiddle(frontArrLeft, middleArrLeft);
    rootNode.right = restoreTreeByFrontAndMiddle(frontArrRight, middleArrRight);
    return rootNode;
}
console.log(restoreTreeByFrontAndMiddle(frontArr, middleArr));
/**
 * 通过中序和后序来还原二叉树
 * @param middleArr
 * @param endArr
 */
function restoreTreeByEndAndMiddle(middleArr, endArr) {
    // 算法的兼容判断
    if (!middleArr || middleArr.length === 0 || !endArr || endArr.length === 0 || middleArr === endArr) return null;
    // 获取后序的最后一个值为根节点, 获取中序的根节点的位置，分割成左右子树; 获取中序的左子树， 右子树， 获取后序的左子树和右子树
    let rootNode = new NodeTree(endArr[endArr.length - 1]), index = middleArr.indexOf(endArr[endArr.length - 1]),
        middleArrLeft = middleArr.slice(0, index), middleArrRight = middleArr.slice(index + 1, middleArr.length),
        endArrLeft = endArr.slice(0, index), endArrRight = endArr.slice(index, endArr.length - 1);
    rootNode.left = restoreTreeByEndAndMiddle(middleArrLeft, endArrLeft);
    rootNode.right = restoreTreeByEndAndMiddle(middleArrRight, endArrRight);
    return rootNode;
}
console.log(restoreTreeByEndAndMiddle(middleArr, endArr));
结果如下：