给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1] 输出：[-1]
思路 根据两个顺序构造一个唯一的二叉树，以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
第一步：如果数组大小为零的话，说明是空节点了。
第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
第五步：切割后序数组，切成后序左数组和后序右数组
第六步：递归处理左区间和右区间
难点就是如何切割，以及边界值找不好很容易乱套。
首先要切割中序数组，为什么先切割中序数组呢？
切割点在后序数组的最后一个元素，就是用这个元素来切割中序数组的，所以必要先切割中序数组。
中序数组相对比较好切，找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割，如下代码中我坚持左闭右开的原则：
int middleIndex;
//找到中序遍历的切割点
for(middleIndex=inorderStart;middleIndex<inorderEnd;middleIndex++){
if(inorder[middleIndex]==rootVal) break;
}
接下来切割后序数组。
首先后序数组的最后一个元素指定不能要了，这是切割点 也是 当前二叉树中间节点的元素，已经用了。
后序数组的切割点怎么找？
后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。
此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。
中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。
/**
* 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 buildTree(int[] inorder, int[] postorder) {
if(inorder.length==0||postorder.length==0) return null;
return traversal(inorder,postorder,0,inorder.length,0,postorder.length);
}
TreeNode traversal(int[] inorder,int[] postorder,int inorderStart,int inorderEnd,int postorderStart,int postorderEnd){
if(postorderStart==postorderEnd){
return null;
}
int rootVal=postorder[postorderEnd-1];
TreeNode root=new TreeNode(rootVal);
int middleIndex;
//找到中序遍历的切割点
for(middleIndex=inorderStart;middleIndex<inorderEnd;middleIndex++){
if(inorder[middleIndex]==rootVal) break;
}
int leftInoederStart=inorderStart;
int leftInoederEnd=middleIndex;
int rightInorderStart=middleIndex+1;
int rightInorderEnd=inorderEnd;
int leftPostorderStart=postorderStart;
int leftPostorderEnd=postorderStart+(middleIndex-inorderStart);
int rightPostorderStart=leftPostorderEnd;
int rightPostorderEnd=postorderEnd-1;
root.left= traversal(inorder,postorder,leftInoederStart,leftInoederEnd,leftPostorderStart,leftPostorderEnd);
root.right=traversal(inorder,postorder,rightInorderStart,rightInorderEnd,rightPostorderStart,rightPostorderEnd);
return root;
}
}
