题解：从前序和中序遍历构造二叉树

解题思路

题目给定了二叉树的前序遍历和中序遍历序列，我们需要从这两种遍历序列中恢复出原始的二叉树结构，并最终返回该树的层序遍历结果。

首先，回顾二叉树的前序遍历和中序遍历的特点：

1. 前序遍历：先访问根节点，再递归访问左子树，最后访问右子树。其顺序为：根 -> 左子树 -> 右子树。
2. 中序遍历：递归访问左子树，再访问根节点，最后访问右子树。其顺序为：左子树 -> 根 -> 右子树。

Leetcode 47.从前序与中序遍历序列构造二叉树-原题链接

题目内容

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

输入描述

• 输入的第一行包含两个整数 $n，m$ ，表示前序遍历数组 $preorder$ 和中序遍历数组 $inorder$ 的长度。
• 第二行包含 $n$ 个整数，表示前序遍历数组 $preorder$。
• 第三行包含 $m$ 个整数，表示中序遍历数组 $inorder$。

输出描述

输出一个数组，表示构造出的二叉树的层序遍历结果。末尾不保留多余null

样例1

输入

5 5
3 9 20 15 7
9 3 15 20 7

输出

3 9 20 null null 15 7

样例2

输入

1 1
-1
-1

输出

-1

提示

• $1 <= preorder.length <= 3000$
• $inorder.length == preorder.length$
• $-3000 <= preorder[i], inorder[i] <= 3000$
• $preorder$ 和 $inorder$均 无重复 元素
• $inorder$ 均出现在 $preorder$
• $preorder$ 保证为二叉树的前序遍历序列
• $inorder$保证 为二叉树的中序遍历序列