由两种遍历序列确定二叉树(多种方法及其优化方法)_先序遍历后序遍历确定二叉树

若已知任意两种遍历序列，是否可以唯一确定一颗二叉树？
答：只要这两种序列包含一个中序序列就可以。
为什么一个先序和一个后序序列无法确定？
答：先序 根左右
后序 左右根
若一棵树，其中一个或多个结点的左子树或右子树为空，那么此时无法判断到底是左子树为空还是右子树为空，就会出现两种情况。
例：先序和中序遍历序列来确定一棵二叉树
解法：
 根据先序遍历序列第一个结点确定根结点；
 根据根结点在中序遍历序列中分割出左右两个子序列
 对左子树和右子树分别递归使用相同的方法继续分解。
注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

3
1

/
9 20
/
15 7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
代码1：简洁但是比较浪费空间

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(
1
2
3
4
5
6