1. 法一：递归

1. 因为后序遍历[9,15,7,20,3]是左右中，它表示一个区间中，最后一个结点，是中间结点。比如[9,15,7,20,3]这个区间，正好是整个二叉树，共5个结点。那么这个区间的中间结点，也就是根节点为最后一个结点3.
2. 而中序遍历[9,3,15,20,7]是左中右，它表示，只要找到中间结点，就可以分出左右两个区间来，比如[9,3,15,20,7]这个区间，已知3是根节点，那么[9]在其左子树，[15,20,7]在其右子树
3. 所以思路很简单，我们先通过后序遍历序列，在区间中拿到最后一个结点，从而获取中间结点。然后通过中序遍历序列，获得其左右两个区间
4. 然后其左右两个区间，因为后序遍历是左右中，中确定后，先确定右区间。

继续从后序遍历序列中，获取其最后一个结点20，20就是这个右子树的中间结点。

5. 然后构造其左区间。依次类推，直到整颗二叉树完成构造。

后序遍历序列只需要从后往前依次遍历即可，因为只需要你做一遍后序遍历，就会发现，后序遍历的效果就是每一个中间结点，都按顺序排列在序列末尾

1. 比如[9,15,7,20,3],根节点为3，3的右子树为20，20的右子树为7，此时通过中序遍历发现右边到头了
2. 开始左子树构造，20的左子树为15, 然后15到头了。回到3 , 最后3的左子树为9. 9也到头了，没有结点了，构造完成

所以一定要注意，拿到中间结点后，先去右区间，右区间遍历完成后，再去左区间

/*** 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 {int post_idx;//当前区间中结点的位置int[] postorder;//后序遍历int[] inorder;//中序//保存中序遍历中，每个结点在inorder数组中的下标Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();//后序：左右中//中序：左中右//每次确定一个“中”public TreeNode buildTree(int[] inorder, int[] postorder) {this.postorder = postorder;this.inorder = inorder;// 从后序遍历的最后一个元素开始：因为后序：左右中，中结点始终在区间最后面post_idx = postorder.length - 1;// 建立（元素，下标）键值对的哈希表，保存中序inorder数组的结点下标位置int idx = 0;for (Integer val : inorder) {idx_map.put(val, idx++);}//helper通过中序和后序遍历构造二叉树，//每次在中序遍历的inorder数组规定区间，初始是全部从0到inorder.length-1//然后从后序遍历中获取中结点。return helper(0, inorder.length - 1);}public TreeNode helper(int in_left, int in_right) {// 如果这里没有节点构造二叉树了，就结束if (in_left > in_right) {return null;}// 选择 post_idx 位置的元素作为当前子树根节点int root_val = postorder[post_idx];//中结点，从后序遍历中获取TreeNode root = new TreeNode(root_val);// 根据 root 所在位置分成左右两棵子树int index = idx_map.get(root_val);//获取此结点在中序遍历中的位置//从而得到以此结点为中心的左右两个区间// 下标减一post_idx--;//下标前移，找到下一个中结点// 先构造右子树（先右区间）root.right = helper(index + 1, in_right);//进入当前中结点的右区间，再次构造// 构造左子树(然后再左区间)root.left = helper(in_left, index - 1);//进入当前中结点的左区间，再次构造return root;//返回当前root结点（中结点）。最终一定会返回根节点}}

2. 法二：迭代

1. 将中序和后序都反过来：中序变为右中左，后序变成右左中
2. 初始我们可以直接通过后序获取根结点root
3. 而如果我们倒着遍历中序序列的话，正好获得到root的右区间
4. 当我们发现倒着遍历中序，找到了root，那么剩下的是左区间的
5. 然后重复这个过程即可

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {if (postorder == null || postorder.length == 0) {//没有结点直接返回nullreturn null;}//后序序列最后一个，必然是根节点TreeNode root = new TreeNode(postorder[postorder.length - 1]);//根节点Deque<TreeNode> stack = new LinkedList<TreeNode>();//模拟栈stack.push(root);//根结点先入栈，是迭代法必须得int inorderIndex = inorder.length - 1;//中序遍历的下标for (int i = postorder.length - 2; i >= 0; i--) {//除去根节点外，依次从后往前遍历postorder后序序列int postorderVal = postorder[i];//获取后序序列，中结点TreeNode node = stack.peek();//获取栈顶元素//下面的inorder[inorderIndex]，指向的是当前node中间结点的右区间最后一个元素if (node.val != inorder[inorderIndex]) {//如果栈顶不是中间结点，直到中序遍历找到中间node.right = new TreeNode(postorderVal);//那么先处理右区间stack.push(node.right);//入队列} else {//如果栈顶就是中间结点//如果没有遍历完成，并且栈顶就是当前中序遍历中间结点的话while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();//出栈这个中间结点node1，它们已经构造完成了右子树，该处理它的左子树了inorderIndex--;//但是如果inorderIndex再次对上栈顶，说明node1这个结点没有左子树，还会继续while循环}//然后处理左区间node.left = new TreeNode(postorderVal);stack.push(node.left);}}return root;}
}