算法题--二叉树重建

551 阅读2分钟

问题:

根据二叉树的前序遍历{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6},重新构建二叉树。

思路:

遍历顺序:

  • 前序遍历:首先访问根,再先序遍历左子树,最后先序遍历右子树。
  • 中序遍历:首先中序遍历左子树,再访问根,最后中序遍历右子树。
  • 后序遍历:首先后序遍历左子树,再后序遍历右子树,最后访问根。

所以有了前序遍历和中序遍历一定可以确定唯一的二叉树,前序遍历的pre[0]就是根节点的位置,所以先在中序遍历中找到根节点的位置,然后根节点的左边就是中序遍历的左子树,右边就是中序遍历的右子树,左子树和右子树同样也是中序遍历,使用递归得到最终结果。

代码实现:

function reConstructBinaryTree(pre, vin) {
    if (!pre || pre.length === 0) {
        return;
    }
    var treeNode = {
        root: pre[0]
    }
    for(var i = 0; i < pre.length; i++) {
        if (vin[i] === pre[0]) {
            // left递归体中的两个参数,是前序变量的左子树和终须变量的左子树
            treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));
            // right递归体中的两个参数,是前序变量的右子树和终须变量的右子树
            // 因为第i个是根节点,需要跳过
            treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));
        }
    }
    return treeNode;
    console.log(treeNode)
}

思考:

如果给定中序遍历和后序遍历,同样可以重建二叉树,只不过由前序遍历的第一项是根节点变成了后序遍历的最后一项是根节点。同样找到中序遍历中根节点的位置,然后进行递归。

代码实现:

function reConstructBinaryTree(vin, pos) {
    if (!pos || pos.length === 0) {
        return;
    }
    var treeNode = {
        root: pos[pos.length-1]
    }
    for(var i = 0; i < pos.length; i++) {
        if (vin[i] === pos[pos.length-1]) {
            // left递归体中的两个参数,是前序变量的左子树和终须变量的左子树
            treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i));
            // right递归体中的两个参数,是前序变量的右子树和终须变量的右子树
            // 因为第i个是根节点,需要跳过
            treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1));
        }
    }
    return treeNode;
    console.log(treeNode)
}