# 从中序与后序遍历序列构造二叉树

给定两个整数数组 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]

提示:

# 思路分析：

没看过 “ 从前序与中序遍历序列构造二叉树 " 可以先看下，从这个文章中我们知道了前序遍历可以很容易的找到某一层的根节点因为根节点的值是最先打印的但是光靠前序遍历我们看不出来这个根节点它的左右孩子是左边还是右边的，所以我们需要结合着中序遍历才能分辨出左右孩子的位置

而中序遍历配合后序遍历还原二叉树也比较简单，我们只需要通过后序遍历的最后一个值就是根节点因为后序遍历顺序为：左，右，值　。　然后再通过中序遍历来分辨根节点左右孩子的位置即可。

	class Solution {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
	// 判断中序和后序是否有元素，如果没有就返回 null
	if(inorder.length == 0 \|\| postorder.length == 0) return null;
	// 通过后序遍历数组的最后一个元素获取二叉树的根节点
	int rootValue = postorder[postorder.length - 1];
	// 将 root 节点存入创建的节点对象中
	TreeNode root = new TreeNode(rootValue);
	// 循环中序数组
	for(int i = 0; i < inorder.length; i++) {
	// 判断如果中序数组第 i 个索引值等于根节点就执行代码
	if(inorder[i] == rootValue) {
	// 复制一个数组元素为：inorder 数组的 0 到 i - 1 区间的元素，也就是当前根节点的左子树
	int inLeft[] = Arrays.copyOfRange(inorder, 0, i);// 9
	// 复制一个数组元素为：inorder 数组的 i + 1 到 inorder.length - 1 区间的元素，也就是当前根节点的右子树
	int inRight[] = Arrays.copyOfRange(inorder, i + 1, inorder.length);// 15,20,7
	// 复制一个数组，元素为：postorder 数组的 0 到 i - 1 区间的元素，也就是当前根节点的左子树
	int postLeft[] = Arrays.copyOfRange(postorder, 0, i);// 9
	// 复制一个数组，元素为：postorder 数组的 i 到 postorder.length - 1 区间的元素，也就是当前根节点的右子树
	int postRight[] = Arrays.copyOfRange(postorder, i, postorder.length - 1);// 15,7,20
	root.left = buildTree(inLeft, postLeft);// 9
	root.right = buildTree(inRight, postRight);// 20
	break;
	}
	}
	return root;
	}
	}