P4064.从前序与中序遍历序列构造二叉树
Leetcode 105.从前序与中序遍历序列构造二叉树
题目描述
给定两个整数数组 preorder 和 inorder，其中 preorder 是一棵二叉树的前序遍历序列，inorder 是同一棵树的中序遍历序列。
请你根据这两个遍历序列构造出原二叉树，并输出该二叉树的层序遍历结果。
二叉树中所有结点的值均不重复。
输入描述
输入共 3 行。
第 1 行包含两个整数 n 和 m，分别表示数组 preorder 和数组 inorder 的长度。
第 2 行包含 n 个整数，表示二叉树的前序遍历序列 preorder。
第 3 行包含 m 个整数，表示二叉树的中序遍历序列 inorder。
保证 n=m，且 preorder 和 inorder 可以唯一构造出一棵二叉树。
输出描述
输出构造出的二叉树的层序遍历结果。
结点之间用空格分隔，空结点用 null 表示。
输出时需要保留中间的 null，但可以省略末尾多余的 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 保证为二叉树的中序遍历序列。
