首页 > 试题广场 >

重建二叉树

[编程题]重建二叉树
  • 热度指数：1327089 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。


提示:
1.vin.length == pre.length
2.pre 和 vin 均无重复元素
3.vin出现的元素均出现在 pre里
4.只需要返回根结点，系统会自动输出整颗树做答案对比
数据范围：，节点的值
要求：空间复杂度 ，时间复杂度
示例1

输入

[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

输出

{1,2,3,4,#,5,6,#,7,#,#,8}

说明

返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示
示例2

输入

[1],[1]

输出

{1}
示例3

输入

[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

输出

{1,2,5,3,4,6,7}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
推荐
欲风头像 欲风 
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    	TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    	return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
    	
    	if(startPre>endPre||startIn>endIn)
    		return null;
    	TreeNode root=new TreeNode(pre[startPre]);
    	
    	for(int i=startIn;i<=endIn;i++)
    		if(in[i]==pre[startPre]){
    			root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
    			root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                      break;
    		}
    			
    	return root;
    }
}

编辑于 2018-03-21 14:58:42 回复(255)
Javascript
BunnyUp头像 BunnyUp 
function reConstructBinaryTree(pre, vin)
{
    // write code here
    //退出及边界条件
    if(pre.length===0||vin.length===0)
        return null
    //     ⅰ. 前序遍历的0号位置确定根
    //     ⅱ. 确定中序遍历的0号元素对应的位置
    const index = vin.indexOf(pre[0]),
    left = vin.slice(0,index),
    right = vin.slice(index+1)
    //     ⅲ. 根据上一步所得的位置将中序数组分割
//     ⅳ. 根据上一步的分割结果将前序数组切割
//     ⅴ. 递归，重复上述步骤
    return{
        val:pre[0],
        left:reConstructBinaryTree(pre.slice(1,index+1),left),
        right:reConstructBinaryTree(pre.slice(index+1),right),
    };
    
}

发表于 2022-04-19 18:41:06 回复(0)
Javascript
十味一心头像 十味一心 
function reConstructBinaryTree(pre, vin)
{
    if(pre.length===0||vin.length===0)return null;
    var index=vin.indexOf(pre[0]);          //找到根节点
    var left=vin.slice(0,index);            //左子树的中序序列
    var right=vin.slice(index+1);           //右子树的中序遍历
    var node=new TreeNode(pre[0]);
    node.left=reConstructBinaryTree(pre.slice(1,index+1),left);
    node.right=reConstructBinaryTree(pre.slice(index+1),right);
    return node;
}

发表于 2021-09-01 21:15:59 回复(0)
Javascript
一个小前端丶头像 一个小前端丶
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    // write code here
    if( pre.length == 0 || vin.length == 0) {
        return null
    }
    let root = pre[0];
    let index = vin.findIndex(v => v === pre[0]);
    let vin_left = vin.slice(0,index);
    let vin_right = vin.slice(index+1);
    let pre_left = pre.slice(1,index+1);
    let pre_right  = pre.slice(index+1)
    return {
        val:root,
        left:reConstructBinaryTree(pre_left,vin_left),
        right:reConstructBinaryTree(pre_right,vin_right)
    }
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};
发表于 2021-07-24 09:48:52 回复(0)
JavaScript
pro给一个offer吧头像 pro给一个offer吧 
function reConstructBinaryTree(pre, vin)
{
    if(!pre.length || !vin.length) {
        return null;
    }
    // 1、获取到树的根节点的value值
    let root = new TreeNode(pre[0]);
    // 2、构建left左子树, right右子树
    // 2.1、找到根节点的index值
    let rValue = root.val;
    let index = vin.indexOf(rValue);
    // 2.2、root.left = reConstructBinaryTree(左子树的前序遍历, 左子树的中序遍历);
    let leftPre = pre.slice(1, index + 1);
    let leftVin = vin.slice(0, index);
    root.left = reConstructBinaryTree(leftPre, leftVin);
    // 2.3、root.right = reConstructBinaryTree(右子树的前序遍历, 右子树的中序遍历);
    let rightPre = pre.slice(index + 1);
    let rightVin = vin.slice(index + 1);
    root.right = reConstructBinaryTree(rightPre, rightVin);
    // 3、返回重建好的二叉树
    return root;
}

发表于 2021-07-12 12:22:30 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function reConstructBinaryTree(pre, vin)
{
    // write code here
    //先找出根节点，然后分割成左子树和右子树，再分别对左右子树递归做同样的操作
    if (pre.length === 0 || vin.length === 0) {
        return null;
    }
    var index = vin.indexOf(pre[0]),
        left = pre.slice(1,index + 1),
        right = pre.slice(index + 1);
    return {
        val : pre[0],
        left : reConstructBinaryTree(left,vin.slice(0,index)),
        right : reConstructBinaryTree(right,vin.slice(index + 1))
    };
}

发表于 2021-04-05 12:23:29 回复(0)
JavaScript
webchang头像 webchang
使用JavaScript： 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

function reConstructBinaryTree(pre, vin)
{
    // 递归的结束条件
    if(!pre.length || !vin.length) return null;
    
    // 先序遍历序列的第一个结点（0号位置）的值就是当前树的根结点
    let value = pre[0];
    let node = new TreeNode(value);
    
    // 获取当前树的根节点在中序遍历的位置index
    // 在先序遍历序列中，1号位置到index是左子树中的，index+1到最后都是右子树中的
    // 在中序遍历序列中，index前边的都是左子树中的，index后边的都是右子树中的
    let index = vin.indexOf(value);
    
    // 递归左子树
    node.left = reConstructBinaryTree(pre.slice(1,index + 1), vin.slice(0,index));
    
    // 递归右子树
    node.right = reConstructBinaryTree(pre.slice(index + 1),vin.slice(index + 1));
    
    return node;
}
编辑于 2021-03-20 21:26:31 回复(0)
JavaScript
Don`tgiveup头像 Don`tgiveup
JS 递归实现 
function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pre, vin)
{
    // write code here
    function dg(p,v){
        if(p.length <= 0){
            return null;
        }
        let middle = p[0];
        let middleIndex = v.indexOf(middle);
        let leftVin = v.slice(0,middleIndex);
        let rightVin = v.slice(middleIndex+1);
        let leftPre = p.slice(1,leftVin.length+1);
        let rightPre = p.slice(1+leftVin.length);
        let pNode = new TreeNode(middle);
        pNode.left = dg(leftPre,leftVin)
        pNode.right = dg(rightPre,rightVin)
        return pNode;
    }
    return  dg(pre, vin);
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};


发表于 2021-01-15 17:18:05 回复(0)
JavaScript
别卷啦！头像 别卷啦！ 
function reConstructBinaryTree(pre, vin)
{
    // write code here   
    if(pre.length === 0 || vin.length === 0)return null
    let root = new TreeNode(pre[0]), i = vin.indexOf(pre[0])
    root.left = reConstructBinaryTree(pre.slice(1, i + 1), vin.slice(0, i))
    root.right = reConstructBinaryTree(pre.slice(i + 1), vin.slice(i + 1))
    return root
}

发表于 2021-01-07 20:29:09 回复(0)
JavaScript
咚咚咚，开门，查水表头像 咚咚咚，开门，查水表 
function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pre, vin)
{
    if (pre.length === 0 || vin.length === 0) return null
    let node = new TreeNode(pre.shift())
    let index = vin.indexOf(node.val)
    node.left = reConstructBinaryTree(pre, vin.slice(0, index))
    node.right = reConstructBinaryTree(pre, vin.slice(index+1))
    return node
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};
编辑于 2020-09-13 13:33:50 回复(0)
JavaScript
chika23头像 chika23 
function reConstructBinaryTree(pre, vin)
{
    if (pre.length == 0) return;
    let rootNode = new TreeNode(pre[0]);
    if (pre.length == 1) return rootNode;
    let i = vin.indexOf(pre[0]);
    let leftZ = vin.slice(0, i);
    let rightZ = vin.slice(i + 1);
    let leftX = pre.slice(1, 1 + i);
    let rightX = pre.slice(1 + i);
    if (leftZ.length != 0)  rootNode.left = reConstructBinaryTree(leftX, leftZ);
    if (rightZ.length != 0) rootNode.right = reConstructBinaryTree(rightX, rightZ);
    return rootNode;
}

编辑于 2020-03-19 17:22:50 回复(0)
JavaScript
Helianthuswhite头像 Helianthuswhite 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

/**
 * 我的解题思路：
 * 1.前序的第一个肯定是根节点
 * 2.中序中查找根节点位置为X，发现不是开头，说明有左子节点
 * 3.前序根节点后一个即是左子节点
 * 4.位置X发现不是结尾，说明有右子节点
 * 5.前序中X加1位置即为根的右子节点
 * 6.前序和中序中移除根节点，递归遍历左右子节点
 *
 * @param {*} pre 
 * @param {*} vin 
 */
function reConstructBinaryTree(pre, vin)
{
    // write code here
    const result = {};
    if (pre.length) {
        const x = vin.indexOf(pre[0]);
        result.val = pre[0];
        
        pre.shift();
        vin.splice(x, 1);

        result.left = reConstructBinaryTree(pre.slice(0, x), vin.slice(0, x));
        result.right = reConstructBinaryTree(pre.slice(x), vin.slice(x));
    }
    return result.val ? result : null;
}

/**
 * 社区TOP1的解题思路：
 * 跟我的思路一致，只是使用了一个额外的方法
 *
 * @param {*} pre 
 * @param {*} vin 
 */
function topReConstructBinaryTree(pre, vin)
{
    // write code here
    const innerFunc = (preStart, preEnd, vinStart, vinEnd) => {
        if (preStart > preEnd || vinStart > vinEnd) {
            return null;
        }

        const result = {val: pre[preStart]};
        for (let i = vinStart; i <= vinEnd; i++) {
            if (pre[preStart] === vin[i]) {
                result.left = innerFunc(preStart + 1, preStart + i - vinStart, vinStart, i - 1)
                result.right = innerFunc(preStart + i - vinStart + 1, preEnd, i + 1, vinEnd);
            }
        }
        return result;
    };

    return innerFunc(0, pre.length - 1, 0, vin.length - 1);
}

发表于 2020-02-14 23:39:02 回复(0)
JavaScript
Bytedancer2021头像 Bytedancer2021 
function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function reConstructBinaryTree(pre, vin)
{
    // write code here
    if(pre.length === 1){
        let node = new TreeNode(pre[0]);
        return node;
    }else{
        let index = vin.indexOf(pre[0]);
        let leftPre = pre.slice(1, index+1);
        let righyPre = pre.slice(index+1, pre.length);
        let leftVin = vin.slice(0, index);
        let rightVin = vin.slice(index+1, vin.length);
        let node = new TreeNode(pre[0]);
        if(leftPre.length){
            node.left = reConstructBinaryTree(leftPre, leftVin);
        }
        if(righyPre.length){
            node.right = reConstructBinaryTree(righyPre, rightVin);
        }
        return node;
    }
}

发表于 2019-09-16 15:17:57 回复(0)
JavaScript
果果爱编程头像 果果爱编程
利用递归，找到根节点，划分左右子树
function reConstructBinaryTree(pre, vin)
{
    if(pre.length==0||vin.length==0){
        return null;
    };
    //前序第一个是根节点，也是中序左右子树的分割点
    let index=vin.indexOf(pre[0]),
        left=vin.slice(0,index),
        right=vin.slice(index+1);
    return {
        val:pre[0],
        //递归左右子树的前序、中序
        left:reConstructBinaryTree(pre.slice(1,index+1),left),
        right:reConstructBinaryTree(pre.slice(index+1),right)
    };
}

发表于 2019-07-21 17:01:02 回复(0)
JavaScript
一只骑单车的猫头像 一只骑单车的猫

JavaScript
递归思想

        function reConstructBinaryTree(pre, vin) {
            // write code here
            var head = new TreeNode(pre[0]),
                headIndex = vin.indexOf(pre[0]),
                leftVin = vin.slice(0, headIndex),
                rightVin = vin.slice(headIndex + 1),
                leftPre = pre.slice(1, 1 + leftVin.length),
                rightPre = pre.slice(1 + leftVin.length);
            if(leftPre.length != 0){
                head.left = reConstructBinaryTree(leftPre, leftVin);
            }
            if(rightPre.length !=0 ){
                head.right = reConstructBinaryTree(rightPre, rightVin);
            }
            return head;
        }
发表于 2019-05-07 17:38:04 回复(0)
JavaScript
kuwii头像 kuwii
与前面大佬们的思路大同小异，
对Node的版本只补充一点：记得把注释里的TreeNode的定义代码取消注释…… 
// Node版本不加这个会报错找不到TreeNode……
function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
// 以下是答案
function reConstructBinaryTree(pre, vin)
{
    var build = function(pl, pr, vl, vr) {
        if (pl > pr || vl > vr) { return null; }
        var firstVal = pre[pl++];
        var node = new TreeNode(firstVal);
        var vm = vin.indexOf(firstVal);
        var vDist = vm - vl;
        node.left  = build(pl, pl+vDist-1, vl, vm-1);
        node.right = build(pl+vDist, pr, vm+1, vr);
        return node;
    }
    return build(0, pre.length-1, 0, vin.length-1);
}
module.exports = {
    reConstructBinaryTree : reConstructBinaryTree
};

发表于 2019-04-03 16:33:58 回复(0)
JavaScript
另类藏在我心中头像 另类藏在我心中
function reConstructBinaryTree(pre, vin) { var t=function(pre,vin){ if(pre.length==0||vin.length==0) return null; if(pre.length==1||vin.length==1) return new TreeNode(pre[0]); var root=new TreeNode(pre[0]); root.left=t(pre.slice(1,vin.indexOf(pre[0])+1),vin.slice(0,vin.indexOf(pre[0]))); root.right=t(pre.slice(vin.indexOf(pre[0])+1),vin.slice(vin.indexOf(pre[0])+1)); return root; } return t(pre,vin); }
发表于 2019-03-29 15:27:52 回复(0)
JavaScript
明月照大江.头像 明月照大江. 
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
    var parse = function(pre, vin) {
        var node = null,
            pos,
            leftPre, leftVin,
            rightPre, rightVin;
        
        if (pre.length !== 0) {
            node = {};
            node.val = pre[0];
            
            pos = vin.indexOf(node.val);
            leftPre = pre.slice(1, pos+1);
            leftVin = vin.slice(0, pos);
            node.left = parse(leftPre, leftVin);
            rightPre = pre.slice(pos+1);
            rightVin = vin.slice(pos+1);
            node.right = parse(rightPre, rightVin);
        }
        return node;
    };
    
    return parse(pre, vin);
}

发表于 2019-01-28 21:26:04 回复(0)
提交观点

问题信息

数组 树 dfs
难度：
45条回答 304837浏览

热门推荐

通过挑战的用户

查看代码

相关试题

重建二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号