今天学习的算法是给定一颗树的中序遍历和后序遍历两个结果数组，构造成一颗二叉树。

题目介绍

如下图所示，给定两个数组，一个是中序遍历后的输出结果，一个是后序遍历的输出结果。需要根据两个数组构造二叉树。

二叉树-根据中序和后序遍历结果构造二叉树-题目.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