二叉树节点定义
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
DFS 深度优先（递归）
// 前序：根 → 左 → 右
void preorder(TreeNode *root) {
if (!root) return;
cout << root->val; // 先处理根
preorder(root->left);
preorder(root->right);
}
// 中序：左 → 根 → 右（BST 输出有序序列）
void inorder(TreeNode *root) {
if (!root) return;
inorder(root->left);
cout << root->val;
inorder(root->right);
}
// 后序：左 → 右 → 根（用于删除、计算高度）
void postorder(TreeNode *root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val;
}
// 复杂度：时间 O(n)，空间 O(h)（递归栈，h 为树高）
DFS 迭代版
// 前序迭代（栈模拟递归）
void preorderIter(TreeNode *root) {
if (!root) return;
stack<TreeNode *> st;
st.push(root);
while (!st.empty()) {
auto *node = st.top(); st.pop();
cout << node->val;
if (node->right) st.push(node->right); // 右先进后出
if (node->left) st.push(node->left);
}
}
// 中序迭代（走到最左，回溯）
void inorderIter(TreeNode *root) {
stack<TreeNode *> st;
auto *cur = root;
while (cur || !st.empty()) {
while (cur) { st.push(cur); cur = cur->left; } // 一路向左
cur = st.top(); st.pop();
cout << cur->val;
cur = cur->right; // 转向右子树
}
}
// 后序迭代（前序的逆：根→右→左 的反转）
void postorderIter(TreeNode *root) {
if (!root) return;
stack<TreeNode *> st;
vector<int> result;
st.push(root);
while (!st.empty()) {
auto *node = st.top(); st.pop();
result.push_back(node->val);
if (node->left) st.push(node->left);
if (node->right) st.push(node->right);
}
reverse(result.begin(), result.end()); // 反转得后序
for (int v : result) cout << v;
}
BFS 层序遍历
void levelOrder(TreeNode *root) {
if (!root) return;
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
int n = q.size(); // 当前层节点数
for (int i = 0; i < n; ++i) {
auto *node = q.front(); q.pop();
cout << node->val;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << '\n'; // 换层
}
}
// 时间 O(n)，空间 O(w)（w 为最宽层节点数）
Morris 遍历（O(1) 空间）
// 中序 Morris：利用叶子节点的空右指针做线索
void morrisInorder(TreeNode *root) {
auto *cur = root;
while (cur) {
if (!cur->left) {
cout << cur->val; // 无左子树，访问当前
cur = cur->right;
} else {
auto *pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) { // 建立线索
pre->right = cur;
cur = cur->left;
} else { // 删除线索
pre->right = nullptr;
cout << cur->val;
cur = cur->right;
}
}
}
}
// O(1) 额外空间，但遍历过程中临时修改了树结构
遍历结果重建树
已知前序 + 中序 → 可唯一确定二叉树
已知后序 + 中序 → 可唯一确定二叉树
已知前序 + 后序 → 不唯一（需要树是满的才行）
前序: [3, 9, 20, 15, 7]
中序: [9, 3, 15, 20, 7]
→ 根是 3（前序第一个）
→ 中序中 3 左边 [9] 是左子树，右边 [15,20,7] 是右子树
→ 递归构建
遍历应用场景
| 遍历 | 典型应用 |
|---|
| 前序 | 序列化、复制树 |
| 中序 | BST 有序输出、验证 BST |
| 后序 | 删除树、计算子树高度 |
| 层序 | 最短路径（无权图 BFS）、宽度 |