vlambda博客
学习文章列表

4. 重建二叉树

        输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

1、思路

        通常树有如下几种遍历方式：

        前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。（root一般在最前）

        中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。（root一般在中间）

        后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。（root一般在最后）

        本题为前序遍历和中序遍历，最少需要两种遍历方式，才能重建二叉树。

        前序遍历序列中，第一个数字总是树的根结点的值。在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。剩下的我们可以递归来实现，具体如图：

        用数学归纳法的思想就是，假设最后一步，就是root的左右子树都已经重建好了，那么我只要考虑将root的左右子树安上去即可。

        根据前序遍历的性质，第一个元素必然就是root，那么下面的工作就是如何确定root的左右子树的范围。

        根据中序遍历的性质，root元素前面都是root的左子树，后面都是root的右子树。那么我们只要找到中序遍历中root的位置，就可以确定好左右子树的范围。                    正如上面所说，只需要将确定的左右子树安到root上即可。递归要注意出口，假设最后只有一个元素了，那么就要返回。

# 输入：[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]。输出：{1,2,5,3,4,6,7}