【数据结构与算法】二叉树遍历 集合

前序遍历（Preorder）：根 → 左 → 右

中序遍历（Inorder）：左 → 根 → 右

后序遍历（Postorder）：左 → 右 → 根

记忆技巧：“前中后”指的是根节点被访问的顺序

什么时候无法唯一确定？

结论：只有先序 + 后序不能唯一确定二叉树，其他组合都能唯一确定。

详细说明

能唯一确定的组合

不能唯一确定的组合

为什么先序 + 后序不能唯一确定？

例子

假设先序 =[1, 2]，后序 =[2, 1]

可能的二叉树：

text

情况1： 1 情况2： 1 / \ 2 2

两种情况都能得到相同的先序和后序！

根本原因

先序是[根, 左子树, 右子树]
后序是[左子树, 右子树, 根]

当某棵子树为空时，你无法判断：

• 先序中的第二个节点是左子树的根还是右子树的根

• 后序中的倒数第二个节点是左子树的根还是右子树的根

1.

#include<iostream> using namespace std; void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root = postorder.back(); cout << root; int rootpos = inorder.find(root); string leftinorder = inorder.substr(0, rootpos); string leftpostorder = postorder.substr(0, leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder = inorder.substr(rootpos+1); string rightpostorder = postorder.substr(leftpostorder.size(),rightinorder.size()); getpreorder(rightinorder, rightpostorder); } int main() { string inorder, postorder; cin >> inorder >> postorder; getpreorder(inorder, postorder); return 0; }

已知中序 + 后序求前序遍历（思路清晰版）

这道题属于二叉树遍历的经典问题，看起来是字符串操作，实际上核心是对三种遍历顺序的理解。

一、问题描述

给定：

• 中序遍历（inorder）

• 后序遍历（postorder）

要求输出：

• 前序遍历（preorder）

二、三种遍历的关系

在做这类题之前，一定要清楚三种遍历的顺序：

• 前序：根 → 左 → 右

• 中序：左 → 根 → 右

• 后序：左 → 右 → 根

这里最关键的一点是：

👉后序遍历的最后一个元素一定是当前树的根节点

三、核心思路

整个过程其实就是一个递归拆分的过程。

1. 确定根节点

后序遍历的最后一个字符就是根节点：

char root = postorder.back();

2. 在中序中定位根

在中序遍历中找到这个根节点的位置：

int rootpos = inorder.find(root);

此时中序会被分成三部分：

左子树 | root | 右子树

3. 切分左右子树

根据中序的位置，可以确定左右子树的范围。

左子树：

string leftinorder = inorder.substr(0, rootpos); string leftpostorder = postorder.substr(0, leftinorder.size());

右子树：

string rightinorder = inorder.substr(rootpos + 1); string rightpostorder = postorder.substr(leftinorder.size(), rightinorder.size());

关键点在于：

👉后序的前一部分长度，等于左子树的节点数量

4. 递归处理

按照前序遍历的顺序：

1. 先输出根节点

2. 再递归左子树

3. 最后递归右子树

cout << root; getpreorder(leftinorder, leftpostorder); getpreorder(rightinorder, rightpostorder);

四、完整代码

#include<iostream> using namespace std; void getpreorder(string inorder, string postorder) { if (inorder.empty()) return; char root = postorder.back(); cout << root; int rootpos = inorder.find(root); string leftinorder = inorder.substr(0, rootpos); string leftpostorder = postorder.substr(0, leftinorder.size()); getpreorder(leftinorder, leftpostorder); string rightinorder = inorder.substr(rootpos + 1); string rightpostorder = postorder.substr(leftinorder.size(), rightinorder.size()); getpreorder(rightinorder, rightpostorder); } int main() { string inorder, postorder; cin >> inorder >> postorder; getpreorder(inorder, postorder); return 0; }

五、举例说明

输入：

inorder = DBEAFC postorder = DEBFCA

过程：

• 根节点：A

• 中序分为：DBE | A | FC

继续递归拆分：

最终得到前序遍历：

ABDECF

六、复杂度分析

时间复杂度：O(n²)

因为每次都要在中序中查找根节点位置。

2.

#include<iostream> #include<vector> using namespace std; void getpostorder(string inorder, string preorder) { if (inorder.empty()) return; char root = preorder[0]; int rootpos = inorder.find(root); string leftinorder = inorder.substr(0, rootpos); string leftpreorder = preorder.substr(1, leftinorder.size()); getpostorder(leftinorder, leftpreorder); string rightinorder = inorder.substr(rootpos+1); string rightpreorder = preorder.substr(1+leftpreorder.size(), rightinorder.size()); getpostorder(rightinorder, rightpreorder); cout << root; } int main() { string inorder, preorder; cin >> inorder >> preorder; getpostorder(inorder, preorder); return 0; }

已知中序 + 前序求后序遍历（思路详解）

这道题和“中序 + 后序求前序”是完全对称的一类题，核心依然是对三种遍历顺序的理解。

一、题目描述

给定：

• 中序遍历（inorder）

• 前序遍历（preorder）

要求输出：

• 后序遍历（postorder）

二、三种遍历关系

必须先明确三种遍历顺序：

• 前序：根 → 左 → 右

• 中序：左 → 根 → 右

• 后序：左 → 右 → 根

这题最关键的一点是：

前序遍历的第一个元素一定是根节点

三、核心思路

整个过程就是不断“找根 + 切分 + 递归”。

1. 确定根节点

char root = preorder[0];

前序第一个就是当前树的根

2. 在中序中找到根

int rootpos = inorder.find(root);

中序结构：

左子树 | root | 右子树

3. 切分左右子树

左子树：

string leftinorder = inorder.substr(0, rootpos); string leftpreorder = preorder.substr(1, leftinorder.size());

右子树：

string rightinorder = inorder.substr(rootpos + 1); string rightpreorder = preorder.substr(1 + leftpreorder.size(), rightinorder.size());

关键点：

前序中，根后面的部分，前一段一定是左子树

4. 递归 + 输出顺序

后序遍历是：

左 → 右 → 根

所以顺序是：

getpostorder(leftinorder, leftpreorder); getpostorder(rightinorder, rightpreorder); cout << root;

四、完整代码

#include<iostream> using namespace std; void getpostorder(string inorder, string preorder) { if (inorder.empty()) return; char root = preorder[0]; int rootpos = inorder.find(root); string leftinorder = inorder.substr(0, rootpos); string leftpreorder = preorder.substr(1, leftinorder.size()); getpostorder(leftinorder, leftpreorder); string rightinorder = inorder.substr(rootpos + 1); string rightpreorder = preorder.substr(1 + leftpreorder.size(), rightinorder.size()); getpostorder(rightinorder, rightpreorder); cout << root; } int main() { string inorder, preorder; cin >> inorder >> preorder; getpostorder(inorder, preorder); return 0; }

五、举例说明

输入：

inorder = DBEAFC preorder = ABDECF

过程：

• 根：A

• 中序分：DBE | A | FC

递归展开后，最终得到：

DEBFCA

六、和另一题的对比（重点理解）

本质完全一样，只是“找根的位置不同”

七、复杂度分析

时间复杂度：O(n²)

原因：

• 每次find()是 O(n)

3.

#include<iostream> using namespace std; long long getcount(string preorder, string postorder) { if (preorder.empty()) return 1; if (preorder.size() == 1) return 1; char root = preorder[0]; char leftroot = preorder[1]; int posleft = postorder.find(leftroot); int leftsize = posleft + 1; string leftpreorder = preorder.substr(1, leftsize); string leftpostorder = postorder.substr(0,leftsize); string rightpreorder = preorder.substr(leftsize+1); string rightpostorder = postorder.substr(leftsize, preorder.size() - 1 - leftsize); long long result = getcount(leftpreorder, leftpostorder) * getcount(rightpreorder,rightpostorder); if (leftpreorder.empty() || rightpreorder.empty()) { result=result * 2; } return result; } int main() { string preorder, postorder; cin >> preorder >> postorder; long long ans=getcount(preorder, postorder); cout << ans; return 0; }

已知前序 + 后序，二叉树有多少种？（本质讲解）

这道题看起来是在“构造树”，其实本质是在问：

给定前序和后序遍历，这棵二叉树有多少种可能结构？

一、先说结论（非常重要）

前序 + 后序 不能唯一确定一棵二叉树

原因：

无法判断某个节点是左孩子还是右孩子

二、举个最简单的例子

preorder = AB postorder = BA

可能的树有两种：

情况1： A / B 情况2： A \ B

两种结构，但遍历完全一样

三、核心问题

什么时候会产生“多种情况”？

当某个节点只有一个孩子时

因为：

这个孩子可以是左，也可以是右

四、你的代码在干什么

你的函数：

long long getcount(string preorder, string postorder)

返回的是：当前子树的可能数量

五、递归核心逻辑

1. 确定根节点

char root = preorder[0];

前序第一个一定是根

2. 找左子树的根

char leftroot = preorder[1];

前序第二个，一定是“左子树的根”（如果存在）

3. 在后序中定位左子树范围

int posleft = postorder.find(leftroot); int leftsize = posleft + 1;

后序中：

左子树 | 右子树 | root

所以posleft + 1就是左子树大小

4. 切分左右子树

5. 递归计算

long long result = getcount(leftpreorder, leftpostorder) * getcount(rightpreorder, rightpostorder);

左右子树是独立的：

总方案数 = 左 × 右

六、最关键的一步（灵魂）

if (leftpreorder.empty() || rightpreorder.empty()) { result = result * 2; }

这一句才是这题的核心

为什么要 ×2？

如果：

只有左子树 或 只有右子树

说明：

这个子树只有一个孩子

那么：

可以是：

• 左孩子

• 右孩子

两种情况！

七、递归的本质

你整个过程其实在做：

一边拆树，一边统计“有多少个单子节点”

每出现一个“单孩子节点”：

方案数 ×2

八、举个完整例子

preorder = ABC postorder = CBA

结构：

A | B | C

每个节点都只有一个孩子：

A 有一个孩子
B 有一个孩子

总共 2 个不确定点：

结果 = 2² = 4

九、复杂度分析

时间复杂度：

O(n²)

原因：

• 每次find()是 O(n)

十、这题的本质总结

统计“单子节点”的个数

每出现一个：

答案 × 2