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

大家好，欢迎来到IT知识分享网。

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

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

问题是什么？

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

关键知识点：三种遍历方式

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

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

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

解题思路：递归分割法

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

1. 确定根节点：前序遍历序列的第一个元素一定是当前树的根节点。
2. 分割左右子树：在中序遍历序列中找到根节点的位置，根节点左边的所有元素构成左子树的中序遍历序列，右边的所有元素构成右子树的中序遍历序列。
3. 确定左右子树的前序序列：根据中序遍历中左子树的节点数量，在前序遍历序列中，根节点后面的对应数量的元素就是左子树的前序遍历序列，剩下的元素则是右子树的前序遍历序列。
4. 递归重建：对左子树和右子树分别重复上述步骤，直到序列为空，此时递归结束。

代码实现

C++版本

/ * 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<int> pre, vector<int> vin) { if (pre.size() == 0) { // 如果序列为空，返回空指针 return NULL; } // 定义存储左右子树遍历序列的容器 vector<int> left_pre, right_pre, left_vin, right_vin; // 前序遍历的第一个元素是根节点 TreeNode* head = new TreeNode(pre[0]); // 在中序遍历中找到根节点的位置 int root_pos = 0; for (int i = 0; i < pre.size(); i++) { if (pre[0] == vin[i]) { root_pos = i; break; } } // 分割左子树的前序和中序序列 for (int i = 0; i < root_pos; i++) { left_vin.push_back(vin[i]); left_pre.push_back(pre[i + 1]); // 跳过前序序列的根节点 } // 分割右子树的前序和中序序列 for (int i = root_pos + 1; i < pre.size(); i++) { right_vin.push_back(vin[i]); right_pre.push_back(pre[i]); } // 递归重建左右子树 head->left = reConstructBinaryTree(left_pre, left_vin); head->right = reConstructBinaryTree(right_pre, right_vin); return head; } }; 

Python版本

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # 序列为空时，返回None if 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 

总结

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