105. Construct Binary Tree from Preorder and Inorder Traversal

Leetcode link

题目简介

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */

题目给我们一颗树经过先序遍历的数组 preorder 以及中序遍历的数组 inorder

题目要求我们根据这两个数组还原出树并返回

解题思路1

这题有两种解法，首先我们先来看没有经过优化的方法

1. 通过 preorder[0] 确定当前树/子树的根节点
2. 通过 inorder 中 preorder[0] 的位置分割其左子树与右子树的节点
3. 递归调用分别处理左子树与右子树
4. 返回一开始的根节点

时间复杂度：O(n^2)

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
    if (inorder.length === 0) {
        return null
    }
    const rootValue = preorder.shift()
    const rootIdx = inorder.indexOf(rootValue)
    const root = new TreeNode(rootValue)

    root.left = buildTree(preorder, inorder.slice(0, rootIdx))
    root.right = buildTree(preorder, inorder.slice(rootIdx + 1))
    return root
};

解题思路 2

我们通过仔细观察可以发现上面的方法中 寻找 inorder 内元素下标需要 O(n) 的复杂度

如果我们用一个 map 来代替每次寻找下标，可以把这个复杂度省略掉

于是就有了思路 2

时间复杂度：O(n)

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
    const inorderMap = new Map()
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i)
    }
    let preorderIdx = 0

    const buildByRange = (start, end) => {
        if (start > end) {
            return null
        }

        const rootValue = preorder[preorderIdx++]
        const rootIdx = inorderMap.get(rootValue)
        const root = new TreeNode(rootValue)

        root.left = buildByRange(start, rootIdx - 1)
        root.right = buildByRange(rootIdx + 1, end)
        return root
    }

    return buildByRange(0, preorder.length - 1)
};