代码实现还原二叉树

前序中序还原二叉树

const qian = ["a", "c", "f", "g", "b", "d", "e"]
const zhong = ["f", "c", "g", "a", "d", "b", "e"]
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
function f1(qian, zhong) {
    if (qian == null || zhong == null || qian.length == 0 || zhong.length == 0 || qian.length !== zhong.length) return null;
    let root = new Node(qian[0]);  //前序排序第一个是根节点
    let index = zhong.indexOf(root.value)  // 找到根节点在中序遍历中的位置
    let qianLeft = qian.slice(1, 1 + index) //前序遍历中左子树
    let qianRight = qian.slice(1 + index, qian.length) // 前序遍历中右子树
    let zhongLeft = zhong.slice(0, index) // 中序遍历中的左子树
    let zhongRight = zhong.slice(index + 1, zhong.length) // 中序遍历中的右子树
    root.left = f1(qianLeft, zhongLeft) 
    root.right = f1(qianRight, zhongRight)
    return root
}
var root = f1(qian, zhong)
console.log(root.left)
console.log(root.right)

运行结果

中序后序还原二叉树

const zhong = ["f", "c", "g", "a", "d", "b", "e"]
const hou = ["f", "g", "c", "d", "e", "b", "a"]
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
function f1(zhong, hou) {
    if (hou == null || zhong == null || hou.length == 0 || zhong.length == 0 || hou.length !== zhong.length) return null;
    let root = new Node(hou[hou.length - 1]) //后序遍历中的根节点在最后
    let index = zhong.indexOf(root.value) // 获取根节点在中序遍历中的位置
    let zhongLeft = zhong.slice(0, index) // 中序遍历左子树
    let zhongRight = zhong.slice(index + 1, zhong.length) // 中序遍历右子树
    let houLeft = hou.slice(0, index) // 后序遍历左子树
    let houRight = hou.slice(index, hou.length - 1) // 后序遍历右子树
    root.left = f1(zhongLeft, houLeft)
    root.right = f1(zhongRight, houRight)
    return root;
}
var root = f1(zhong,hou)
console.log(root.left)
console.log(root.right)