leetcode 105. 从前序与中序遍历序列构造二叉树 javascript

解题的关键在于要知道前序和中序的区别,
前序是根左右,中序是左根右
比如题目中给到的
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
可以知道根节点是3,然后可以从中序数组中得出左子树和右子树,分别是[9] 和 [15,20,7]
同样,知道左右子树之后,根据其数组长度,可以在前序数组中定位前序的左右子树,分别是[9] 和 [20,15,7],这时候就要用到递归了,直到得到结果
递归的终止条件是,序列为空,返回null
序列只有一个元素(也就是叶子节点),创造新的node,并直接返回,详见代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(!preorder || preorder.length < 1){
        return null;
    }
    let root = preorder[0];
    let treeNode = new TreeNode(root);
    if(preorder.length === 1) {
        return treeNode;
    }
    
    let rootIndex = inorder.indexOf(root);
    let inLeftTree = inorder.slice(0, rootIndex);
    let preLeftTree= preorder.slice(1, inLeftTree.length + 1);
    let inRightTree = inorder.slice(rootIndex + 1, inorder.length);
    let preRightTree = preorder.slice(preLeftTree.length + 1, preorder.length);
    
    treeNode.left = buildTree(preLeftTree, inLeftTree);
    treeNode.right = buildTree(preRightTree, inRightTree);
    
    return treeNode;
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容