题⽬描述
输⼊某⼆叉树的前序遍历和中序遍历的结果，请重建出该⼆叉树。假设输⼊的前序遍历和中序遍历的结果中都不含重复的数字。例如输⼊前序遍历序列{1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6}，则重建⼆叉树并返回。
思路及解答
递归解决
看上⾯的图⽚，⾸先数据保证了正确性，那么前序的第⼀个肯定是root 节点，也就是1，那么就需要在中序遍历中找到1 的位置，左边就是这个root 的左⼦树，右边就是root 的右⼦树。
举个例子：对根节点的左⼦树进⾏解析：
对右⼦树进⾏解析：
只需要不断递归即可，当边界左边⼤于右边的时候，则停⽌。
栈解法
所有的递归理论上都可以⽤栈模拟，那么我们如何⽤栈解答呢？
我们可以⼀开始创建⼀个栈，分别⽤两个指针执⾏前序遍历和中序遍历的第⼀个元素，先将前序遍历的第⼀个元素压⼊栈中，因为前序遍历的特性，第⼀个元素肯定是根节点。
开始循环，对⽐栈顶的元素和中序遍历数组的元素
如果不相等，说明当前栈顶元素还有左⼦树，因为如果没有左⼦树的话，前序的第⼀个元素和中序的第⼀个元素应该相等。既然有左⼦树，那么前序遍历指针指向的元素就是它的左⼦树根节点，建⽴关系，压栈。
如果相等，那么说明当前的栈顶元素已经没有左⼦树了。
把栈顶元素和中序遍历的元素对⽐，相等则弹出之后，继续对⽐下⼀个元素与当前的栈顶元素，直到不相等为⽌。（相等说明没有右节点，弹出意味着退出上⼀层）
不相等的时候，需要把当前的元素作为右叶⼦节点，压⼊栈中。
上⾯的⽂字可能⽐较难懂，但是不紧要，下⾯图⽂说明：
⾸先我们有前序和中序遍历的数组，原树结构⼤致了解⼀下：
把当前的前序遍历的元素 1 先放到栈⾥⾯，这个肯定是根节点：
对⽐中序遍历第⼀个元素 4，和栈顶元素 1 ,不相等，那么说明有左⼦树，前序遍历的第 2 个元素 2就是左⼦树节点，关联成左⼦树，压栈：
同样得不相等，会持续压栈：
直到，中序遍历的第⼀个元素 4，已经等于栈顶元素 4，说明4 没有左⼦树了，因为 4 是在中序遍历⾥⾯，中序遍历完根节点，剩下的部分只能是右⼦树。
那么把 4 弹出去，中序遍历指针移动到下⼀个位置：
这个时候， 7 肯定是之前节点 4 的右⼦树节点，那么关联关系之后，压⼊栈⾥⾯：
此时，结束了⼀次循环，注意前序遍历的指针会往后移动⼀位。
再次循环的时候，依然判断中序遍历中的数值是否等于栈顶元素，发现都是7 ,相等。弹出，移动到下⼀个位置，相当于退出了上⼀层：
依旧 2==2 相等，再次弹出：
同样中序遍历的 1 还是等于栈顶的 1 ,弹出，移动到下⼀位：
这个时候，栈顶元素的 1 已经被取出来了，说明左⼦树全部遍历完成了，剩下的部分是它的右⼦树内容了，那么前序遍历中， 3 就必定是根节点1 的右⼦树的根，压⼊栈中，前序遍历索引指向下⼀个元素：
到这⾥其实是结束了第⼆轮的循环。
再次循环，判断中序遍历的数值和栈顶元素不相等，那么说明是左⼦树，前序遍历中的 5 压⼊栈内，索引后移：
中序遍历的数值和栈顶元素⼀对⽐，发现相等，说明5 没有左⼦树了，弹出，索引后移：
依然 两个都是 3（说明 3 的左⼦树被遍历完成了，剩下的是 3 的右⼦树了），继续弹出，后移
此时， 3 是刚刚弹出的元素，剩下的元素都是它的右⼦树，那么前序遍历中指向的数组6 就是3 的右⼦树， 6 压⼊栈中：
对⽐栈顶元素6 和中序遍历中的8 发现不相等，那么把前序遍历中的 8 压栈，成为左⼦树：
对⽐栈顶元素 8 和中序遍历的 8，相等则弹出：
还是相等，继续弹出：
栈⾥⾯没有元素，并且数组都遍历结束，整个过程结束。