面试题：重建二叉树

summary

:

这是一个很老很老的题，我做它，就是为了练习，练到能闭着眼睛在纸上写出来。

题目

输入某二叉树的前序遍历和中序遍历的结果，重新建立这棵二叉树，输出它的后序遍历。 假设不含重复数字，类型为int。

分析

根据前序遍历和中序遍历求后序遍历是经典的二叉树问题了，不管是在选择题中还是在 写代码的题中，都会碰到。首先，要人脑会做，而且要有方法做，不是试出来的。主要 的思想是递归。比如前序遍历为1, 2, 4, 7, 3, 5, 6, 8，中序遍历为4, 7, 2, 1, 5, 3, 8, 6，则1肯定为根节点，然后从中序遍历中找到1,则1的左边的数字为左 子树，右边的为右子树。然后，递归下去，左子树的前序遍历为2, 4, 7，中序遍历为 4, 7, 2，则2为左子树的根节点，看中序遍历，则4, 7为这棵左子树的左子树，再递归， 前序遍历和中序遍历都为4, 7，则4为根节点，7为右节点，至此，已完成左边。右边 也是一样的。

我的代码

由于要让函数返回字符串来进行单元测试，比较麻烦，面试的时候肯定不用这样的，面试 关心的是你的算法能力，而不是这些东西。所以我没有用Boost单元测试框架，直接在main 函数里面测试了。

::: {.code-include lexer="cpp"} ./rebuild-binary-tree.cpp :::