leetcode 889 题（中等）

原题链接：
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

题目描述：
给定两个整数数组，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 是同一棵二叉树的前序遍历和后序遍历

解题思路

preorder = [1,2,4,5,3,6,7],
postorder = [4,5,2,6,7,3,1]
前序遍历头左右
后序遍历左右头
根据遍历顺序我们可以确定头节点，
然后在前序遍历中，头节点下一位置2 就是左节点起始位置，
通过2 可以在中序遍历中找到左子树的结束位置
左树确定好了，就可以确定右树了。

代码演示

/*** 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) {int right = preorder.length - 1;return process(preorder,0,right,postorder,0,right);}/*** pre 前序遍历数组* ps 前序遍历起始位置* pe 结束位置* pos  后序遍历数组* hs 后序的起始位置* he 后序的结束位置**/public TreeNode process(int[]pre,int ps,int pe,int[]pos,int hs,int he){//base case 处理越界if(ps > pe || hs > he){return null;}//base case 相等时直接返回。if(ps == pe){return  new TreeNode(pre[ps]);}//直接先拿到头节点TreeNode root = new TreeNode(pre[ps]);//前序遍历中头节点下一个节点是左节点，直接拿到值int leftVal = pre[ps+1];//记录左节点在后序遍历中的位置int index = 0;//根据值比较 确定位置for(int i = hs;i <= he;i++){if(pos[i] == leftVal){index = i;break;}}//计算出左子树的节点数int leftSize = index - hs + 1;//构造左子树root.left = process(pre,ps+1,ps+leftSize,pos,hs,hs+leftSize-1);//构造右子树root.right = process(pre,ps+leftSize+1,pe,pos,index+1,he-1);return root;}
}