来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解答

通过前序遍历和中序遍历得到二叉树：

1. 从前序遍历数组头部获得根节点
2. 从中序遍历数组中获取根节点的左子树和右子树

3. 中序遍历数组的用处：左子树数组为空则左子节点为 null，右子树数组为空则右子节点为 null

   /**
   * 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 (preorder.length && inorder.length) {
        const rootVal = preorder.shift();
        let rootIndex = inorder.indexOf(rootVal);
        const root = new TreeNode(rootVal);
        root.left = buildTree(preorder, inorder.slice(0, rootIndex));
        root.right = buildTree(preorder, inorder.slice(rootIndex + 1));
        return root;
    } else {
        return null;
    }
   };