C++实现剑指offer面试题7：重建二叉树算法详解

在编程面试中，重建二叉树是一个常见的题目，它涉及到数据结构中的二叉树知识以及对递归思维的考察。剑指offer是针对中国程序员编写的一本面试指南书籍，其中面试题（7）特别考察了应聘者对于二叉树结构及操作的理解和编码能力。本篇将详细解析如何使用C++语言来实现重建二叉树的功能。 知识点一：二叉树的基本概念 二叉树是一种重要的数据结构，在计算机科学中广泛应用于查找表、搜索树等场景。它具有以下基本性质： 1. 每个节点最多有两个子节点，称为左子节点和右子节点。 2. 二叉树可以为空，即没有节点。 3. 对于任意一个节点，其左子树和右子树都是二叉树。 4. 二叉树的子树有左右之分，即使某节点只有一个子节点，也需要区分左子树或右子树。 知识点二：二叉树的遍历 在重建二叉树之前，通常需要掌握二叉树的三种基本遍历方法：前序遍历（Preorder）、中序遍历（Inorder）和后序遍历（Postorder）。它们的主要区别在于访问节点的顺序不同： 1. 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。 2. 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。 3. 后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。 知识点三：重建二叉树的原理 重建二叉树，通常是指根据给定的遍历结果（例如前序遍历和中序遍历的结果）来还原原始二叉树结构。前序遍历的第一个元素永远是根节点，而中序遍历中根节点的位置可以将树分为左右子树，据此可以分别对左右子树进行同样的操作，递归地构建整个树。 知识点四：C++语言实现重建二叉树 在C++中实现重建二叉树，首先需要定义二叉树节点的数据结构，然后根据遍历序列递归重建树。 1. 定义二叉树节点结构体： ```cpp struct TreeNode { int val; // 节点存储的值 TreeNode *left; // 指向左子节点的指针 TreeNode *right; // 指向右子节点的指针 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数 }; ``` 2. 根据前序和中序遍历结果重建二叉树的函数实现： ```cpp TreeNode* buildTreeHelper(vector<int>& preorder, int p_start, int p_end, vector<int>& inorder, int i_start, int i_end, unordered_map<int, int>& inMap) { if(p_start > p_end || i_start > i_end) return nullptr; // 前序和中序遍历序列的开始和结束位置不匹配时，返回空节点 TreeNode* root = new TreeNode(preorder[p_start]); // 前序遍历的第一个值是根节点 int inRoot = inMap[root->val]; // 在中序遍历中找到根节点的位置 int numsLeft = inRoot - i_start; // 左子树节点数量 root->left = buildTreeHelper(preorder, p_start + 1, p_start + numsLeft, inorder, i_start, inRoot - 1, inMap); root->right = buildTreeHelper(preorder, p_start + numsLeft + 1, p_end, inorder, inRoot + 1, i_end, inMap); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { unordered_map<int, int> inMap; // 用于快速查找中序遍历中元素的索引 for(int i = 0; i < inorder.size(); i++) { inMap[inorder[i]] = i; } return buildTreeHelper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, inMap); } ``` 知识点五：代码解析 - `buildTree`函数接受前序和中序遍历的结果数组，返回重建后的二叉树根节点。 - `unordered_map<int, int>`是为了提高查找效率，预先存储了中序遍历数组中每个元素的索引。 - `buildTreeHelper`是一个递归函数，它利用了前序和中序遍历的特性来定位根节点，并分割左右子树的遍历数组。 - 在`buildTreeHelper`中，首先确定根节点，然后根据根节点在中序遍历中的位置确定左右子树的大小。 - 根据左子树的大小，调整前序遍历数组的遍历范围，递归地构建左子树和右子树。 - 最终递归调用返回构建好的二叉树的根节点。 通过以上分析，我们可以看出重建二叉树的C++实现依赖于二叉树的性质和遍历算法，以及递归思想的运用。掌握这些知识对于解决类似的编程面试题目至关重要。