本文首发于我的个人博客s ixin s blog 原文: https:s  ct-binary-treel 作者: s ixin 题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树.假设输入的前序遍历和中序遍历的结果中都不含重复的数字.例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回. 解题思路 前序遍历:nlr 中序遍历:lnr 对于前序遍历的结果,若为空,则二叉树为空,若长度为1,则二叉树只有一个结点即为根结点.第一个元素一定为二叉树的根结点.对于中序遍历的结果,根结点所处的位置前面的为左子树的中序遍历结果,右面的为右子树的中序遍历结果.分别可以得到左子树和右子树的结点数量,在前序遍历中数数即可分开左右子树的前序遍历结果.通过递归可重建二叉树.例子: 前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}.分析步骤: 根结点为1,则左子树的中序遍历结果为{4,7,2},右子树的中序遍历结果为{5,3,8,6}; 左子树共有3个结点,则左子树的前序遍历结果为{2,4,7},右子树的前序遍历结果为{3,5,6,8}; 递归分别对左子树和右子树重建二叉树.