題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列[1,2,4,7,3,5,6,8]，和中序遍歷序列[4,7,2,1,5,3,8,6]，則重建二叉樹并返回

實(shí)現(xiàn)思路

根據(jù)前序遍歷和中序遍歷的定義，我們不難發(fā)先輸入數(shù)據(jù)可以進(jìn)行如下拆分

在這里插入圖片描述

既然我們已經(jīng)分別找到了左、右子樹的前序遍歷和中序遍歷，那么我們就可以用同樣的方法分別去構(gòu)建左右子樹，進(jìn)行遞歸推導(dǎo)

代碼實(shí)現(xiàn)

function reConstructBinaryTree(pre, vin) {
        if(pre.length==0||vin.length==0){
                return null;
        };
        
        //前序第一個(gè)為根節(jié)點(diǎn) 也是中序左右子樹的分割點(diǎn)
        var index=vin.indexOf(pre[0]);
        var left=vin.slice(0,index);//中序左子樹
        var right=vin.slice(index+1);//中序右子樹
        
        return {
            val:pre[0],
            //遞歸左右子樹的前序，中序
            left:reConstructBinaryTree(pre.slice(1,index+1),left),
            right:reConstructBinaryTree(pre.slice(index+1),right)
        };
}