从遍历序列到完整二叉树：教你用前序和中序遍历重建二叉树

二叉树是数据结构中的重要成员，而根据遍历序列重建二叉树更是面试中的高频考点。今天就来聊聊如何利用前序遍历和中序遍历的结果，一步步还原出完整的二叉树，还会附上清晰的代码示例哦。

简单来说，就是给定某二叉树的前序遍历序列和中序遍历序列（序列中不含重复数字），要求我们根据这两个序列重建出这棵二叉树。比如已知前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，我们要通过这两个序列把原始的二叉树“画”出来。

在解决问题之前，我们得先明确二叉树的三种常见遍历方式：

前序遍历：先访问根结点，再访问左子结点，最后访问右子结点（根→左→右）。中序遍历：先访问左子结点，再访问根结点，最后访问右子结点（左→根→右）。后序遍历：先访问左子结点，再访问右子结点，最后访问根结点（左→右→根）。

本题用到的是前序遍历和中序遍历，这两种遍历方式结合起来，才能确定唯一的二叉树结构。

重建二叉树的核心思路是利用前序遍历和中序遍历的特性，通过递归不断分割左右子树，具体步骤如下：

确定根节点：前序遍历序列的第一个元素一定是当前树的根节点。分割左右子树：在中序遍历序列中找到根节点的位置，根节点左边的所有元素构成左子树的中序遍历序列，右边的所有元素构成右子树的中序遍历序列。确定左右子树的前序序列：根据中序遍历中左子树的节点数量，在前序遍历序列中，根节点后面的对应数量的元素就是左子树的前序遍历序列，剩下的元素则是右子树的前序遍历序列。递归重建：对左子树和右子树分别重复上述步骤，直到序列为空，此时递归结束。/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {public:TreeNode* reConstructBinaryTree(vector pre, vector vin) {if (pre.size == 0) { // 如果序列为空，返回空指针return NULL;}// 定义存储左右子树遍历序列的容器vector left_pre, right_pre, left_vin, right_vin;// 前序遍历的第一个元素是根节点TreeNode* head = new TreeNode(pre[0]);// 在中序遍历中找到根节点的位置int root_pos = 0;for (int i = 0; i left = reConstructBinaryTree(left_pre, left_vin);head->right = reConstructBinaryTree(right_pre, right_vin);return head;}};# -*- coding:utf-8 -*-# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution:# 返回构造的TreeNode根节点def reConstructBinaryTree(self, pre, tin):# 序列为空时，返回Noneif len(pre) == 0:return None# 序列只有一个元素时，直接返回该节点elif len(pre) == 1:return TreeNode(pre[0])else:# 根节点为前序遍历的第一个元素root = TreeNode(pre[0])# 找到根节点在中序遍历中的位置pos = tin.index(pre[0])# 递归重建左子树和右子树root.left = self.reConstructBinaryTree(pre[1:pos+1], tin[:pos])root.right = self.reConstructBinaryTree(pre[pos+1:], tin[pos+1:])return root

利用前序遍历和中序遍历重建二叉树，关键在于抓住两种遍历方式的特性：前序定根，中序分左右。通过递归的方式不断分割序列、重建子树，就能从两个遍历序列还原出完整的二叉树。这种方法思路清晰，而且代码实现也不复杂，掌握它能帮你在面对二叉树相关问题时更有底气哦！