之前讲到了Tree Traversals Again这道题的一些概念，接下来看一下它的核心算法，

首先我们需要建立另外一个数组，我把它命名为post,这个数组存的就是后续遍历的结果，那我直接要根据这两个数组里面数字分布的情况，把后续遍历的结果，直接写到post数组里面去，这两个数组里面有一件事情是非常好确定的，就是谁是根结点，谁一定是根结点呢？在先序遍历里面，根结点一定是第一个被访问到的，所以在先序这个数组里面，它的第一个元素存的必定是根结点

那么在后续遍历里面，根结点是什么时候被访问到的了？它一定是最后一个被访问到的，所以pre的第一个元素，一定会被放在post最后一个元素的位置上，

所以第一件事情我们就先确定了根结点，把它先填进来了，然后我们就可以分而治之，分别递归的去处理左边和右边的问题，那么这个时候我们的问题就来了，我怎么知道左边包含哪些元素,右边包含哪些元素呢？要搞清楚这件事情，我们就需要依赖于这个中序遍历的结果，很显然中序遍历先访问了左边，然后访问根结点，然后才访问右边的，所以这个根结点在中序遍历里面所处的位置，它在这里

就很自然的把这个问题分成了两块，根结点左边的元素，都一定是属于左子树的，根结点右边的元素，都一定是属于右子树的，这些结点的存储顺序在先序遍历里面多半是不一样的，但至少知道它有多少个

我们会知道从根节点往后，数3个，这3个一定是属于左子树的(2, 3, 4),后面两个一定是属于右子树的(5,6),那以此类推，我也知道在post这个数组里面，前3个元素，不知道它是什么，但它一定存的是左子树的，然后后面两个元素，一定是存的右子树，这个时候我就可以递归的去解决绿色的，左边的问题，然后递归的去解决蓝色的，右边的问题

我们来看一下伪代码，我给这个递归函数取一个很土的名字就叫做solve,我们要传进去的有哪些参数呢？

我需要知道的是preL指的是先序遍历最左边这个元素它的位置，就是它这个数组的下标，那以此类推，inL和postL就分别指的是中序遍历第一个结点的位置和后续遍历第一个结点的位置，然后我还需要知道整个现在要处理的这个数组的规模有多大，n是当前这个数组里面元素的个数，第一件事情我们可以确定根结点是什么，根结点就是pre它最左边的这个元素(root = pre[preL])，所以我们马上可以做的事情，就是把这个root写到post最后一个结点的位置上去，最后一个结点就是postL+n-1,然后我在这个循环里面在干什么呢,我在判断in这个位置上的元素是不是等于根结点，也就是说我要从左到右，去扫描这个数组，要找这个根节点，到底在哪，然后i是从0一直走到n的，在某一个i,这个位置上，如果我找到了这个根结点，那么break,我就跳出这个循环，在跳出这个循环的同时，我也就知道了，它的左子树，到底包含有多少个元素，然后我就要递归的去解决左边和右边的问题，那么在递归之前呢，最好先算出来，左边到底有多少个元素，右边到底有多少个元素，这个也很简单，我们知道从i点跳出来的时候，左边就含有正好i个元素，那右边的元素个数呢，就是当前元素的总个数减去左边的个数，再减掉根结点的个数，现在我们就准备好要递归了，当我们递归调用左边的时候，我们应该传什么参数进去呢?我们要传的是，新的pre最左边的位置，新的pre最左边的位置，是什么？就是2这个位置，它是原来那个preL再加上1这个位置

那对于in和post这两个数组来说，它们最左边的位置都是不变的，所以左边的调用非常简单，我传进去一个新的preL+1,然后in和post都不变，这是左边元素的个数，

右边稍微复杂一点，那右边的第一个元素，它在什么位置上呢？这个元素是在什么位置上呢，它就会是原始的preL加上L,也就是左边元素的个数，再加1，才指向它的第一个位置，in也是一样的道理，也是它原始的inL加上这个元素的个数加上1，对于post来说呢，比它们往前错一位，所以这个就是我们递归调用右边的结果

我们传进来的是preL+L+1,它的第一个位置，inL+L+1是在in里面它的第一个的位置，对于post来说，就是postL+L, 不需要加那个1了，R是右边子问题的总个数，作为一个递归的函数调用，我们有一件非常重要的事情要处理，就是最小的case,最小的case我们要写在最开始的地方，最小的case实际上有两个，一个是当n==0的时候，我什么都不做，直接return，另外是当n == 1,我们只有一个结点的时候，那么肯定的，post,pre,in全部都应该等于同一个数字，那我在这就直接把pre的这个数字写到post里面去，然后return就可以了，在这你有没有想到一个问题，最小的case，n == 1不就可以了吗？为什么还需要n == 0呢？真的会出现n等于0的情况吗？我如果把if (n==0) return去掉了会怎么样呢？你试试看，把这行去掉样例运行出来还对不对，接下来，从头到尾把这个样例过一遍，那我们第一件事情呢，先找到了这个root,然后把它写好，同时我就递归的去调用左边，我会发现左边进来的第一个pre是等于2的，所以2会被写在post的这个位置上。

然后我去找2在in里面的位置，发现它正好在中间，于是我知道它左边有一个3，右边有一个4，那我递归的去调用左边，那这个时候，左边就只有一个结点了，于是post左边应该写3

然后再递归的去调用右边，然后post的2，3中间应该写的是4，这样就完成了左边的递归调用，

当我进入右边递归调用的时候，会发生什么事情呢？会发现pre的第一个元素是5，所以5应该写在这

5在in里面处于最后一个位置，我知道5的左边还有一个6，所以6会被写在这

5的右边呢，5的右边没有元素了，但是你的程序其实不知道的，它会继续递归的去调用右边，这个时候对应的就是n==0的情形，右边一个元素都没有，什么都不做，直接退回，你才能正常结束。