189 8069 5689
题目：
中序遍历特点：先遍历左子树，再遍历根节点，最后遍历右子树
后序遍历特点：先遍历左子树，再遍历右子树，最后遍历根节点
根据后序遍历的特点，我们可以得到postorder数组最后一个元素就是根节点，root = 3，在中序遍历中找到该节点，根据中序遍历的特点就可以找到根节点的左右子树，[9]就是左子树的所有值，[15 , 20 , 7]就是右子树的所有的值。
我们用变量pos_index来从后往前遍历postorder数组（后序遍历序列），初始值为pos_index = postorder.length - 1，因为后序遍历是 左 --->右 --->根 顺序遍历，所以当我们从后往前遍历postorder数组时，先访问的是右子树的节点。
定义递归函数 buildTree(left, right)表示当前递归到中序序列中当前子树的左右边界，递归入口为buildTree(0, n - 1);
按此思路我们用递归实现时，应该先递归创建右子树，在递归创建左子树。
代码如下：
class Solution {
int pos_index;
int[] postorder;
//创建map，来存放中序序列的值和对应的索引值
HashMapinorder_map = new HashMap();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
int index = 0;
//将inorder数组中的元素存放到inorder_map中，方便后面找索引位置
for(Integer value : inorder){
inorder_map.put(value,index++);
}
pos_index = postorder.length - 1;
return buildTree(0,pos_index);
}
public TreeNode buildTree(int left,int right){
//当left >right时，说明分割的子数组中没有节点来构造树了
if(left >right){
return null;
}
//获取后序遍历序列的最后一个元素，并为根节点
int value = postorder[pos_index];
//将pos_index左移
pos_index--;
//封装为根节点
TreeNode root = new TreeNode(value);
//找到value在中序遍历序列的索引
int index = inorder_map.get(value);
//递归创建右子树
root.right = buildTree(index + 1, right);
//递归创建左子树
root.left = buildTree(left,index - 1);
return root;
}
} 总结：主要是利用后序遍历序列来确定根节点，在以此根节点到中序遍历序列中来确定改根节点的左右子树，通过参数left和right来动态变化创建子树的左右边界。
后序遍历实现：
public void postorder(TreeNode root){
if(root == null){
return null;
}
//递归左子树
postorder(root.left);
//递归右子树
postorder(root.right);
//打印根节点
System.out.print(root.val);
}我们通过上述代码得到了后序遍历序列，现在要反向遍历后序序列（因为根据后序遍历特点，根在序列末尾）将其还原成树，就需要将上述代码的遍历过程反向即可（也就是反向的前序遍历 根 ---- 右 --- 左），这也就是为什么要先创建右子树，再创建左子树。利用后序序列我们只能知道根，而不能确定当前根的左右子树的范围，这时候我们就需要借助中序遍历来确定根的子树的边界。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧