美文网首页
leetcode 105. 从前序与中序遍历序列构造二叉树 ja

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

作者: 帅气的名字都被用了了 | 来源:发表于2018-06-24 13:52 被阅读0次

解题的关键在于要知道前序和中序的区别,
前序是根左右,中序是左根右
比如题目中给到的
前序遍历 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;
};

相关文章

网友评论

      本文标题:leetcode 105. 从前序与中序遍历序列构造二叉树 ja

      本文链接:https://www.haomeiwen.com/subject/ognjyftx.html