從前序與中序遍歷序列構(gòu)造二叉樹

解題:

//樹節(jié)點
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var buildTree = function(preorder, inorder) {
    //獲取兩種遍歷數(shù)組長度
    let preLen = preorder.length;
    let inLen = inorder.length;

    //如果長度不對那么有問題返回null
    if(preLen != inLen) return null;

    //將中序數(shù)組存儲到hash表,便于后面利用前序的根節(jié)點找中序的根節(jié)點下標(biāo)
    let map = {};
    for(let i = 0;i < inLen;i++) {
        //數(shù)據(jù)作為鍵,下標(biāo)作為值
        map[inorder[i]] = i;
    }

    //遞歸入口,傳入初始值
    return recursionTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1, map);
}

/**
 * 構(gòu)建下一個節(jié)點
 *
 * @param {*} preorder  前序遍歷
 * @param {*} preLeft   前序遍歷左邊界(包括根)
 * @param {*} preRight  前序遍歷右邊界
 * @param {*} inorder   中序遍歷
 * @param {*} inLeft    中序遍歷左邊界
 * @param {*} inRight   中序遍歷右邊界
 * @param {*} map       中序遍歷哈希表
*/
var recursionTree = function(preorder,preLeft,preRight,inorder,inLeft,inRight,map) {
    //遞歸出口
    if(preLeft > preRight || inLeft > inRight) return null;

    //求中序遍歷的根inRootIndex => 從前序遍歷得到根,到哈希表得到中序遍歷該根的下標(biāo)
    let inRootIndex = map[preorder[preLeft]];
    //求左右子樹 => 中序遍歷inRootIndex下標(biāo)左邊是左子樹,右邊是右子樹
    //根據(jù)左子樹長度求前序遍歷左子樹右邊界x(是個下標(biāo))
    //x - preLeft - 1 = inRootIndex - 1 - inLeft
    let x = inRootIndex + preLeft - inLeft;
            
    //創(chuàng)建新節(jié)點
    let TreeNode = {};
    //新結(jié)點的值就是前序遍歷的根
    TreeNode.val = preorder[preLeft];
    //遞歸建立新節(jié)點的左子樹,這里傳的值是左子樹的前序遍歷和中序遍歷的邊界
    TreeNode.left = recursionTree(preorder,preLeft + 1,x,inorder,inLeft,inRootIndex - 1,map);
    //遞歸建立新節(jié)點的右子樹,這里傳的值是右子樹的前序遍歷和中序遍歷的邊界
    TreeNode.right = recursionTree(preorder,x + 1,preRight,inorder,inRootIndex + 1,inRight,map);
            
    return TreeNode;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容