从前序与中序遍历序列构造二叉树

解题:

//树节点
function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var buildTree = function(preorder, inorder) {
    //获取两种遍历数组长度
    let preLen = preorder.length;
    let inLen = inorder.length;

    //如果长度不对那么有问题返回null
    if(preLen != inLen) return null;

    //将中序数组存储到hash表,便于后面利用前序的根节点找中序的根节点下标
    let map = {};
    for(let i = 0;i < inLen;i++) {
        //数据作为键,下标作为值
        map[inorder[i]] = i;
    }

    //递归入口,传入初始值
    return recursionTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1, map);
}

/**
 * 构建下一个节点
 *
 * @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 => 从前序遍历得到根,到哈希表得到中序遍历该根的下标
    let inRootIndex = map[preorder[preLeft]];
    //求左右子树 => 中序遍历inRootIndex下标左边是左子树,右边是右子树
    //根据左子树长度求前序遍历左子树右边界x(是个下标)
    //x - preLeft - 1 = inRootIndex - 1 - inLeft
    let x = inRootIndex + preLeft - inLeft;
            
    //创建新节点
    let TreeNode = {};
    //新结点的值就是前序遍历的根
    TreeNode.val = preorder[preLeft];
    //递归建立新节点的左子树,这里传的值是左子树的前序遍历和中序遍历的边界
    TreeNode.left = recursionTree(preorder,preLeft + 1,x,inorder,inLeft,inRootIndex - 1,map);
    //递归建立新节点的右子树,这里传的值是右子树的前序遍历和中序遍历的边界
    TreeNode.right = recursionTree(preorder,x + 1,preRight,inorder,inRootIndex + 1,inRight,map);
            
    return TreeNode;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容