假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。...开始循环,对比栈顶的元素和中序遍历数组的元素
2.1 把栈顶元素和中序遍历的元素对比,相等则弹出之后,继续对比下一个元素与当前的栈顶元素,直到不相等为止。...再次循环,判断中序遍历的数值和栈顶元素不相等,那么说明是左子树,前序遍历中的 5 压入栈内,索引后移:
中序遍历的数值和栈顶元素一对比,发现相等,说明5没有左子树了,弹出,索引后移:
依然 两个都是...3(说明 3 的左子树被遍历完成了,剩下的是 3 的右子树了),继续弹出,后移
此时,3 是刚刚弹出的元素,剩下的元素都是它的右子树,那么前序遍历中指向的数组6就是3的右子树,6 压入栈中:
对比栈顶元素...6 和中序遍历中的8 发现不相等,那么把前序遍历中的 8 压栈,成为左子树:
对比栈顶元素 8 和中序遍历的 8 ,相等则弹出:
还是相等,继续弹出:
栈里面没有元素,并且数组都遍历结束,整个过程结束