题目描述
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。
示例 1：
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
示例 2:输入: preorder = [1], postorder = [1]
输出: [1]提示：
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都 不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都 不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历
做题思路
本题重点考察的是如何根据给定的 前序中序的结果去还原二叉树
想要把本题做出来必须要有一定的数据结构的基础，尤其是对二叉树的三种遍历方式有所了解才可以
前序遍历： 根 左 右
中序遍历: 左 根 右
后序遍历: 左 右 根
知道了二叉树的三种遍历方式我们再来看题目，题目中给我们的是二叉树的后序和前序的遍历结果。
我来大概的说一下本题的实现思路;
我们已经知道了前序遍历的话第一次遍历的必定是 根结点
并且前序遍历的第二个结点一定是左子树当中的那个根节点，后续遍历的话是是先遍历左子树当中最后的那最左边的那个结点，然后再遍历右子树
通过这个左子树的根节点我们就可以到题目中给出的后序遍历的数组里面去寻找这个根节点，找到了这个根节点之后我们就可以得知这颗二叉树左子树一共有多少个结点以及右子树有多少个结点了(也可以理解为左或右子树的长度了)
然后我们就可以通过递归来接着上一步的操作继续的去执行，直到把先序数组全部都遍历完成，就可以结束开始回调了
这里有一个细节，就是当前序遍历的 i==j 的时候，也就是已经遍历到最后一个结点了，这个时候就可以直接返回了
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
return work(preorder,0,preorder.length-1,postorder,0,postorder.length-1);
}
public TreeNode work(int[] preorder,int i,int j,int[] postorder,int p,int q){
if(i>j)return null;
TreeNode root=new TreeNode(preorder[i]);
if(i==j)return root;
int r=p;
while(preorder[i+1]!=postorder[r])r++;
int leftLen=r-p+1;
TreeNode left=work(preorder,i+1,i+leftLen,postorder,p,r);
TreeNode right=work(preorder,i+leftLen+1,j,postorder,r+1,q-1);
root.left=left;
root.right=right;
return root;
}
}