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

[Ray-56]

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

题目

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

        3
       / \
      9  20
         / \
        15  7

[Ray-56]

// preorder  父-左-右
// inorder   左-父-右
var buildTree = function(preorder, inorder) {
    if (inorder.length === 0) return null;

    const root = new TreeNode(preorder[0]);
    const mid = inorder.indexOf(preorder[0]);
    root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
    root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
    return root;
};