二叉树的还原

// 给出前序、中序还原二叉树，并写出后序遍历
// 前序遍历：A CFGBDE       
// 中序遍历：FCG A DBE     
const forward = ['a', 'c', 'f', 'g', 'b', 'd', 'e'];
const middle = ['f', 'c', 'g', 'a', 'd', 'b', 'e'];

function Node(value){
    this.value = value;
    this.left = null;
    this.right = null;
}


function f1(forward, middle){
    if(forward == null || middle == null || forward.length == 0 || middle.length == 0 || forward.length != middle.length){
        return null;
    }
    let root = new Node(forward[0]);
    let index = middle.indexOf(root.value); // 找到根节点在中序遍历中的位置
    let fLeft = forward.slice(1, 1 +index); // 前序遍历的左子树
    let fRight = forward.slice(1 +index, forward.length); // 前序遍历的右子树
    let mLeft = middle.slice(0, index); // 中序遍历的左子树
    let mRight = middle.slice(1 + index, middle.length);   // 中序遍历的右子树
    root.left = f1(fLeft, mLeft);   // 根据左子树的前序和中序还原左子树并赋值给 root.left
    root.right = f1(fRight, mRight);    // 根据右子树的前序和中序还原右子树并赋值给 root.right
    return root;
}

const root = f1(forward, middle);
console.log(root);

// 根据后序、中序还原二叉树，并写出前序遍历
// 中序遍历： FCG A DBE
// 后序遍历： FGCDEB A

// const forward = ['a', 'c', 'f', 'g', 'b', 'd', 'e'];
const middle = ['f', 'c', 'g', 'a', 'd', 'b', 'e'];
const behind = ['f', 'g', 'c', 'd', 'e', 'b', 'a'];

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

function f2(behind, middle) {
    if (behind == null || middle == null || behind.length == 0 || middle.length == 0 || behind.length != middle.length) {
        return null;
    }
    let root = new Node(behind[behind.length - 1]);
    let index = middle.indexOf(root.value);
    let bLeft = behind.slice(0, index);
    let bRight = behind.slice(index, behind.length - 1);
    let mLeft = middle.slice(0, index);
    let mRight = middle.slice(index + 1, middle.length);
    root.left = f2(bLeft, mLeft);
    root.right = f2(bRight, mRight);
    return root;
}

const root = f2(behind, middle);
console.log(root);