本课时有配套视频讲解，购买后即可观看（永久有效）
还原二叉树
一、课上练习
编程练习
二、知识总结
✨ 已知先序遍历和中序遍历求后序遍历
已知二叉树的先序遍历和中序遍历序列，可以通过特定的方法来构造出该树的后序遍历序列。这个过程涉及到递归地分割这些遍历序列，以正确地重建整个树的结构，然后产生后序遍历序列。
算法步骤
- 确定根节点：在先序遍历中，序列的第一个元素总是树的根节点。
- 在中序遍历中找到根节点：中序遍历中根节点的位置将树分为左子树和右子树。
- 划分子树：根据中序遍历中根节点的位置，确定左子树和右子树的中序遍历序列。在先序遍历中也相应地划分出左子树和右子树的序列（根据左子树的节点数目，从根节点后紧接的部分开始）。
- 递归重复：对左子树和右子树，重复上述步骤，直到所有子树都被处理。
- 后序遍历输出：对于任何一子树或树，后序遍历的顺序是：先左子树，然后右子树，最后是根节点。
下面的代码展示了根据给定的先序遍历和中序遍历序列来输出后序遍历：
先序+中序求后序遍历代码示例
1#include <iostream>
2#include <vector>
3#include <iterator>
4using namespace std;
5
6// 寻找中序遍历中的根节点位置
7int findPosition(vector<int>& inorder, int element, int start, int end) {
8 for (int i = start; i <= end; i++) {
9 if (inorder[i] == element) return i;
10 }
11 return -1;
12}
13
14// 主要函数，用于构建后序遍历
15void buildPostorder(vector<int>& preorder, vector<int>& inorder, int start, int end, vector<int>& postorder) {
16 static int preIndex = 0;
17 if (start > end) return;
18 // 找到当前根节点，并递增先序索引
19 int element = preorder[preIndex++];
20 int pos = findPosition(inorder, element, start, end);
21 // 递归构建左子树
22 buildPostorder(preorder, inorder, start, pos - 1, postorder);
23 // 递归构建右子树
24 buildPostorder(preorder, inorder, pos + 1, end, postorder);
25 // 添加当前根节点到后序遍历结果中
26 postorder.push_back(element);
27}
28
29int main() {
30 vector<int> preorder = {1, 2, 4, 5, 3, 6, 7}; // 例子中的先序遍历
31 vector<int> inorder = {4, 2, 5, 1, 6, 3, 7}; // 例子中的中序遍历
32 vector<int> postorder; // 存储后序遍历的结果
33 buildPostorder(preorder, inorder, 0, inorder.size() - 1, postorder);
34 cout << "Postorder traversal is: ";
35 for (int i : postorder) {
36 cout << i << " ";
37 }
38 cout << endl;
39 return 0;
40}注意事项
- 递归解决方案在理论上很直观，但在实际应用中需要注意栈溢出的问题，尤其是在处理非常大的树时。
- 上述代码假定所有树的节点值都是唯一的，这样可以在中序遍历中正确地识别根节点。
这种从先序和中序遍历结果构建后序遍历的方法非常有用，特别是在不需要构造实际树结构的场景下，如一些算法竞赛或解决特定的编程问题中。
✨ 执行示例
下面通过一个具体例子，展示"已知先序和中序求后序"的完整递归过程。
已知：
- 先序遍历：A B D E C F
- 中序遍历：D B E A F C
第 1 步：确定根节点
- 先序第一个元素是 A，所以 A 是根节点
- 在中序中找到 A 的位置：D B E A F C
- A 左边 [D B E] 是左子树（3 个节点），A 右边 [F C] 是右子树（2 个节点）
- 先序中，A 后面 3 个元素 [B D E] 是左子树的先序，再后面 [C F] 是右子树的先序
第 2 步：递归处理左子树（先序 B D E，中序 D B E）
- 先序第一个 B 是左子树的根
- 中序中找到 B：D B E
- B 的左子树：[D]（1 个节点），右子树：[E]（1 个节点）
第 3 步：递归处理 B 的左子树（先序 D，中序 D）
- 只有一个节点 D，它是叶子节点
第 4 步：递归处理 B 的右子树（先序 E，中序 E）
- 只有一个节点 E，它是叶子节点
第 5 步：递归处理右子树（先序 C F，中序 F C）
- 先序第一个 C 是右子树的根
- 中序中找到 C：F C
- C 的左子树：[F]（1 个节点），右子树：空
第 6 步：递归处理 C 的左子树（先序 F，中序 F）
- 只有一个节点 F，它是叶子节点
还原的树：
A
/ \
B C
/ \ /
D E F后序遍历（左右根）：D E B F C A
✨ 已知后序遍历和中序遍历求先序遍历
已知二叉树的后序遍历和中序遍历序列，重建该树并得到其先序遍历的序列是一个有趣的问题，通常在数据结构和算法的学习中会被提到。
基本思想
- 后序遍历的最后一个元素为树的根节点。
- 在中序遍历序列中找到该根节点，这将序列分为左子树和右子树。
- 在后序遍历序列中根据左右子树的大小确定左子树和右子树的序列。
- 递归地对左子树和右子树重复上述过程，直到所有子树都被处理。
- 根据重建的二叉树，执行先序遍历以产生先序遍历序列。
算法步骤
- 确定根节点：从后序遍历序列的末尾获取根节点。
- 分割中序遍历序列：在中序遍历序列中查找根节点的位置，该位置将序列分为左右子树。左子树中的元素位于根节点的左侧，右子树的元素位于根节点的右侧。
- 分割后序遍历序列：根据中序遍历中左右子树的长度，从后序遍历序列中分离出左右子树的序列。注意后序遍历的根节点已被移除。
- 递归构建：对左子树和右子树递归地重复上述步骤，构建整个树结构。
- 生成先序遍历：使用先序遍历的规则（根 -> 左 -> 右）递归地遍历重建的二叉树。
下面的代码展示了根据后序遍历和中序遍历序列重建二叉树并执行先序遍历：
后序+中序求先序遍历代码示例
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12// Helper function to find the index of value in inorder vector
13int findInOrderIndex(vector<int>& inorder, int start, int end, int value) {
14 for (int i = start; i <= end; i++) {
15 if (inorder[i] == value) return i;
16 }
17 return -1;
18}
19
20// Recursive function to build the binary tree
21TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int& postIndex) {
22 if (inStart > inEnd) return NULL;
23 // Create the root node with the current postIndex
24 TreeNode* node = new TreeNode(postorder[postIndex--]);
25 // If this node has no children then return
26 if (inStart == inEnd) return node;
27 // Find the index of this node in inorder traversal
28 int inIndex = findInOrderIndex(inorder, inStart, inEnd, node->val);
29 // Recursively construct the right and then left subtree
30 node->right = buildTree(inorder, postorder, inIndex + 1, inEnd, postIndex);
31 node->left = buildTree(inorder, postorder, inStart, inIndex - 1, postIndex);
32 return node;
33}
34
35// Function to do preorder traversal
36void preOrder(TreeNode* node) {
37 if (node == NULL) return;
38 cout << node->val << " ";
39 preOrder(node->left);
40 preOrder(node->right);
41}
42
43int main() {
44 vector<int> inorder = {9, 3, 15, 20, 7};
45 vector<int> postorder = {9, 15, 7, 20, 3};
46 int postIndex = postorder.size() - 1;
47 TreeNode* root = buildTree(inorder, postorder, 0, inorder.size() - 1, postIndex);
48 cout << "Preorder traversal of the constructed tree is: ";
49 preOrder(root);
50 cout << endl;
51
52 return 0;
53}这个代码通过递归方式根据后序和中序遍历结果重建二叉树，并通过先序遍历输出重建后的树的节点。通过这种方法，我们能够从给定的遍历序列中准确地重建原始的树结构。
✨ 解题步骤详解
当你遇到"已知两种遍历求第三种遍历"的问题时，按以下步骤操作：
前提条件： 必须有中序遍历作为其中一种已知序列。只知道先序和后序无法唯一确定二叉树。
方法一：先序 + 中序 -> 后序
- 先序的第一个元素就是当前子树的根。
- 在中序中定位这个根，将中序分为左子树部分和右子树部分。
- 根据左子树节点个数，在先序中也划分出左、右子树的先序序列。
- 递归处理左子树和右子树。
- 按"左、右、根"的顺序输出即得后序遍历。
方法二：后序 + 中序 -> 先序
- 后序的最后一个元素就是当前子树的根。
- 在中序中定位这个根，划分左右子树。
- 注意递归时要先处理右子树再处理左子树（因为后序序列从后往前读时，先遇到的是右子树的根）。
- 按"根、左、右"的顺序输出即得先序遍历。
✨ 常见错误
- 在中序遍历中找不到根节点：通常是因为输入数据有误或节点值不唯一。算法假设所有节点值各不相同。
- 先序/后序中左右子树的划分位置计算错误：左子树的节点个数由中序遍历中根节点的位置决定，必须用这个数量来划分先序/后序序列，不能凭感觉。
- static 变量导致多次调用出错：代码示例中使用了
static int preIndex，如果需要多次调用函数，这个变量不会重置。建议改用引用参数传递索引。 - 后序 + 中序还原时递归顺序错误：必须先递归右子树，再递归左子树（因为 postIndex 从后往前递减，后序中右子树的根在左子树的根之后）。
- 只知道先序和后序就尝试还原：先序和后序不能唯一确定一棵二叉树（除非每个非叶节点都恰好有两个子节点）。
三、课后练习
编程练习
- 二叉树遍历：L3243