今天学习的算法是给定一颗树的中序遍历和后序遍历两个结果数组，构造成一颗二叉树。
题目介绍
如下图所示，给定两个数组，一个是中序遍历后的输出结果，一个是后序遍历的输出结果。需要根据两个数组构造二叉树。
二叉树-根据中序和后序遍历结果构造二叉树-题目.png
实现思路
老规矩，先看下实现思路图：
二叉树-根据中序和后序遍历结果构造二叉树-解题.png
首先说下中序数组和后序数组的特点吧：
1.后序数组的最后一个节点是根节点。
2.中序数组中，处于根节点左侧的节点是左子树节点，处于根节点右侧的节点是右子树节点。
从上图中可以看到，解题的主要思路如下：
1.先找到后序数组的最后一个节点，这个节点就是根节点。
2.通过根节点将中序数组拆分为两个数组，同时将后序数组也拆分为两个数组。
3.然后将上述拆分出来的四个数组两两一组，成为新的中序和后序数组。
4.将上述两组数组重新按第1步操作。最终当数组长度为1时无需再拆分。
代码实现还是使用递归的方式，按之前说过的递归代码最重要的是两点： 1、找到递归公式 2、找到终止条件
根据上述分析过程，可以得出以下两点：
1、递归公式：F(inorder[len],postorder[len]) =Node(mid) + F(inorder[0,mid],postorder[0,mid]) + F(inorder[mid+1,len],postorder[mid+1,len]);
2、终止条件：postorder[] 数组长度为1时。
本次的解题思路有点复杂，包括代码也有点复杂，后序优化下。
实现代码
public class SolutionConsturtFromInorderAndPostorder {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (postorder.length == 1) {
return new TreeNode(postorder[0]);
}
int midVal = postorder[postorder.length - 1];
TreeNode midNode = new TreeNode(midVal);
int midIndex = 0;
while (inorder[midIndex] != midVal) {
midIndex++;
}
if (midIndex > 0) {
int[] inorderLeft = new int[midIndex];
int[] postorderLeft = new int[midIndex];
for (int i = 0; i < midIndex; i++) {
inorderLeft[i] = inorder[i];
postorderLeft[i] = postorder[i];
}
midNode.left = buildTree(inorderLeft, postorderLeft);
}
if (midIndex < inorder.length - 1) {
int[] inorderRight = new int[inorder.length - 1 - midIndex];
int[] postorderRight = new int[inorder.length - 1 - midIndex];
for (int i = 0; i < inorderRight.length; i++) {
inorderRight[i] = inorder[midIndex+1];
postorderRight[i] = postorder[midIndex];
midIndex++;
}
midNode.right = buildTree(inorderRight, postorderRight);
}
return midNode;
}
}
算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms
