递归和迭代实现三种二叉树遍历
利用线索二叉树思想，空间复杂度达到O(1)，但会临时修改树结构。：日常用递归，深度大时用标准迭代，追求极致空间用Morris。：对于深度很大的树，递归可能导致栈溢出，应优先使用迭代法。：因为根节点最后访问，无法像前序、中序那样简单处理。：最直观，利用"根-右-左"反转得到"左-右-根"：使用pair标记访问状态，适用于所有遍历方式。：访问顺序是左子树 → 根节点 → 右子树。：访问顺序是左子树 →
·
先序遍历二叉树
1. 定义二叉树节点结构
#include <iostream>
#include <vector>
#include <stack>
#include <utility>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};2. 递归法
class Solution {
public:
// 递归先序遍历
std::vector<int> preorderRecursive(TreeNode* root) {
std::vector<int> result;
dfs(root, result);
return result;
}
private:
void dfs(TreeNode* node, std::vector<int>& result) {
if (!node) return;
result.push_back(node->val); // 访问根节点
dfs(node->left, result); // 遍历左子树
dfs(node->right, result); // 遍历右子树
}
};3. 迭代法（单栈法）
class Solution {
public:
// 迭代先序遍历 - 使用栈
std::vector<int> preorderIterative(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
std::stack<TreeNode*> stack;
stack.push(root);
while (!stack.empty()) {
TreeNode* node = stack.top();
stack.pop();
result.push_back(node->val); // 访问根节点
// 注意：先右后左，因为栈是LIFO
if (node->right) {
stack.push(node->right); // 右子节点先入栈（后访问）
}
if (node->left) {
stack.push(node->left); // 左子节点后入栈（先访问）
}
}
return result;
}
};4. 迭代法（模拟递归过程）
class Solution {
public:
// 模拟递归调用栈的迭代写法
std::vector<int> preorderIterative2(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
// pair<节点, 是否已访问>
std::stack<std::pair<TreeNode*, bool>> stack;
stack.push({root, false});
while (!stack.empty()) {
auto [node, visited] = stack.top();
stack.pop();
if (!node) continue;
if (visited) {
result.push_back(node->val); // 第二次遇到时访问
} else {
// 逆序入栈：右、左、根
stack.push({node->right, false});
stack.push({node->left, false});
stack.push({node, true}); // 标记为已访问
}
}
return result;
}
};5. 迭代法（手动模拟递归的另一种写法）
class Solution {
public:
// 更接近递归思维的迭代写法
std::vector<int> preorderIterative3(TreeNode* root) {
std::vector<int> result;
std::stack<TreeNode*> stack;
TreeNode* current = root;
while (current || !stack.empty()) {
// 访问左子树直到最左边
while (current) {
result.push_back(current->val); // 访问当前节点
stack.push(current); // 保存节点以便返回到右子树
current = current->left; // 移动到左子节点
}
// 回到父节点，转向右子树
current = stack.top();
stack.pop();
current = current->right;
}
return result;
}
};复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归 | O(n) | O(h)，h为树高 |
| 迭代(标准) | O(n) | O(h) |
| 迭代(模拟递归) | O(n) | O(h) |
| 迭代(手动模拟) | O(n) | O(h) |
要点说明
-
标准迭代法：最简单直观，利用栈的LIFO特性
-
模拟递归法：使用pair标记节点状态，代码模式通用
-
手动模拟法：更接近递归的执行过程，适合理解递归本质
-
栈溢出考虑：对于深度很大的树，递归可能导致栈溢出，应优先使用迭代法
中序遍历二叉树
1. 递归法
#include <iostream>
#include <vector>
#include <stack>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
// 递归中序遍历
std::vector<int> inorderRecursive(TreeNode* root) {
std::vector<int> result;
dfs(root, result);
return result;
}
private:
void dfs(TreeNode* node, std::vector<int>& result) {
if (!node) return;
dfs(node->left, result); // 遍历左子树
result.push_back(node->val); // 访问根节点
dfs(node->right, result); // 遍历右子树
}
};2. 迭代法（单栈法）
class Solution {
public:
// 迭代中序遍历 - 使用栈
std::vector<int> inorderIterative(TreeNode* root) {
std::vector<int> result;
std::stack<TreeNode*> stack;
TreeNode* current = root;
while (current || !stack.empty()) {
// 一直向左走到最左边
while (current) {
stack.push(current);
current = current->left;
}
// 访问最左边的节点
current = stack.top();
stack.pop();
result.push_back(current->val);
// 转向右子树
current = current->right;
}
return result;
}
};3. 迭代法（模拟递归过程）
class Solution {
public:
// 模拟递归调用栈的迭代写法
std::vector<int> inorderIterative2(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
// pair<节点, 是否已访问>
std::stack<std::pair<TreeNode*, bool>> stack;
stack.push({root, false});
while (!stack.empty()) {
auto [node, visited] = stack.top();
stack.pop();
if (!node) continue;
if (visited) {
result.push_back(node->val); // 第二次遇到时访问
} else {
// 逆序入栈：右、根、左
stack.push({node->right, false});
stack.push({node, true}); // 标记为已访问
stack.push({node->left, false});
}
}
return result;
}
};4. 迭代法（颜色标记法-通用模板）
class Solution {
public:
// 颜色标记法：0表示未访问，1表示已访问
std::vector<int> inorderIterative3(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
std::stack<std::pair<TreeNode*, int>> stack;
stack.push({root, 0});
while (!stack.empty()) {
auto [node, color] = stack.top();
stack.pop();
if (!node) continue;
if (color == 0) {
// 未访问：按逆序入栈（右、根、左）
stack.push({node->right, 0});
stack.push({node, 1}); // 标记为已访问
stack.push({node->left, 0});
} else {
result.push_back(node->val); // 已访问，输出
}
}
return result;
}
};5. Morris遍历（空间复杂度O(1)）
class Solution {
public:
// Morris中序遍历 - 空间复杂度O(1)
std::vector<int> inorderMorris(TreeNode* root) {
std::vector<int> result;
TreeNode* current = root;
while (current) {
if (!current->left) {
// 没有左子树，直接访问当前节点
result.push_back(current->val);
current = current->right;
} else {
// 找到左子树的最右节点（前驱节点）
TreeNode* predecessor = current->left;
while (predecessor->right && predecessor->right != current) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
// 建立线索链接
predecessor->right = current;
current = current->left;
} else {
// 已经访问过左子树，断开线索
predecessor->right = nullptr;
result.push_back(current->val);
current = current->right;
}
}
}
return result;
}
};复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 递归 | O(n) | O(h) | 代码简洁 | 可能栈溢出 |
| 标准迭代 | O(n) | O(h) | 安全可控 | 需要手动维护栈 |
| 模拟递归 | O(n) | O(h) | 通用模板 | 稍复杂 |
| 颜色标记 | O(n) | O(h) | 易于理解 | 额外状态标记 |
| Morris | O(n) | O(1) | 空间最优 | 会修改树结构 |
关键要点
-
中序遍历特点：访问顺序是左子树 → 根节点 → 右子树
-
标准迭代法：核心是"一直向左走"，使用栈保存路径
-
与先序遍历的区别：
-
先序遍历：访问节点后再压栈
-
中序遍历：节点出栈时才访问
-
-
Morris遍历：利用线索二叉树思想，空间复杂度达到O(1)，但会临时修改树结构
-
选择建议：日常用递归，深度大时用标准迭代，追求极致空间用Morris
后序遍历（左-右-根）的递归与迭代实现
1. 递归法
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
class Solution {
public:
// 递归后序遍历
std::vector<int> postorderRecursive(TreeNode* root) {
std::vector<int> result;
dfs(root, result);
return result;
}
private:
void dfs(TreeNode* node, std::vector<int>& result) {
if (!node) return;
dfs(node->left, result); // 遍历左子树
dfs(node->right, result); // 遍历右子树
result.push_back(node->val); // 访问根节点
}
};2. 迭代法（双栈法）
class Solution {
public:
// 后序遍历迭代法 - 双栈法
std::vector<int> postorderIterativeDoubleStack(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
std::stack<TreeNode*> stack1, stack2;
stack1.push(root);
// 第一个栈处理节点顺序：根-右-左
while (!stack1.empty()) {
TreeNode* node = stack1.top();
stack1.pop();
stack2.push(node); // 将节点压入第二个栈
// 注意：先左后右，因为第二个栈会反转顺序
if (node->left) stack1.push(node->left);
if (node->right) stack1.push(node->right);
}
// 第二个栈弹出顺序：左-右-根
while (!stack2.empty()) {
result.push_back(stack2.top()->val);
stack2.pop();
}
return result;
}
};3. 迭代法（单栈法-需要记录访问状态）
class Solution {
public:
// 后序遍历迭代法 - 单栈法（需要记录上次访问的节点）
std::vector<int> postorderIterativeSingleStack(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
std::stack<TreeNode*> stack;
TreeNode* current = root;
TreeNode* lastVisited = nullptr;
while (current || !stack.empty()) {
// 一直向左走
while (current) {
stack.push(current);
current = current->left;
}
// 查看栈顶节点
current = stack.top();
// 如果右子树为空或已经访问过，则访问当前节点
if (!current->right || current->right == lastVisited) {
result.push_back(current->val);
stack.pop();
lastVisited = current;
current = nullptr; // 重要：避免重复遍历
} else {
// 否则转向右子树
current = current->right;
}
}
return result;
}
};4. 迭代法（模拟递归过程）
class Solution {
public:
// 模拟递归调用栈的迭代写法
std::vector<int> postorderIterativeSimulate(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
// pair<节点, 是否已访问>
std::stack<std::pair<TreeNode*, bool>> stack;
stack.push({root, false});
while (!stack.empty()) {
auto [node, visited] = stack.top();
stack.pop();
if (!node) continue;
if (visited) {
result.push_back(node->val); // 第二次遇到时访问
} else {
// 逆序入栈：根、右、左（因为栈是LIFO）
stack.push({node, true}); // 标记为已访问
stack.push({node->right, false});
stack.push({node->left, false});
}
}
return result;
}
};5. 迭代法（颜色标记法）
class Solution {
public:
// 颜色标记法：0表示未访问，1表示已访问
std::vector<int> postorderIterativeColor(TreeNode* root) {
std::vector<int> result;
if (!root) return result;
std::stack<std::pair<TreeNode*, int>> stack;
stack.push({root, 0});
while (!stack.empty()) {
auto [node, color] = stack.top();
stack.pop();
if (!node) continue;
if (color == 0) {
// 未访问：按逆序入栈（根、右、左）
stack.push({node, 1}); // 标记为已访问
stack.push({node->right, 0});
stack.push({node->left, 0});
} else {
result.push_back(node->val); // 已访问，输出
}
}
return result;
}
};6. Morris后序遍历（空间复杂度O(1)）
class Solution {
public:
// Morris后序遍历 - 需要反转输出
std::vector<int> postorderMorris(TreeNode* root) {
std::vector<int> result;
TreeNode dummy(0);
dummy.left = root;
TreeNode* current = &dummy;
while (current) {
if (!current->left) {
current = current->right;
} else {
// 找到左子树的最右节点（前驱节点）
TreeNode* predecessor = current->left;
while (predecessor->right && predecessor->right != current) {
predecessor = predecessor->right;
}
if (!predecessor->right) {
// 建立线索链接
predecessor->right = current;
current = current->left;
} else {
// 已经访问过左子树，断开线索并输出左子树路径
predecessor->right = nullptr;
printReversePath(current->left, result);
current = current->right;
}
}
}
return result;
}
private:
// 反转输出从node到其最右节点的路径
void printReversePath(TreeNode* node, std::vector<int>& result) {
int count = 0;
while (node) {
result.push_back(node->val);
node = node->right;
count++;
}
// 反转这部分结果
std::reverse(result.end() - count, result.end());
}
};关键要点
-
后序遍历特点：访问顺序是左子树 → 右子树 → 根节点
-
最难实现：因为根节点最后访问，无法像前序、中序那样简单处理
-
双栈法：最直观，利用"根-右-左"反转得到"左-右-根"
-
单栈法：需要记录上次访问的节点来判断右子树是否已访问
-
通用模板：使用pair标记访问状态，适用于所有遍历方式
-
选择建议：
-
日常开发：递归法
-
生产环境（树很深）：双栈法（简单可靠）
-
追求空间效率：单栈法
-
面试准备：掌握双栈法和单栈法
-
三种遍历方式对比
| 遍历方式 | 递归代码顺序 | 迭代难点 | 常用迭代方法 |
|---|---|---|---|
| 先序遍历 | 根-左-右 | 简单 | 单栈法 |
| 中序遍历 | 左-根-右 | 中等 | 单栈法 |
| 后序遍历 | 左-右-根 | 较难 | 双栈法/标记法 |
各方法复杂度对比
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 递归 | O(n) | O(h) | 代码最简洁 | 可能栈溢出 |
| 双栈法 | O(n) | O(n) | 直观易懂 | 需要两个栈 |
| 单栈法 | O(n) | O(h) | 空间较优 | 逻辑稍复杂 |
| 模拟递归 | O(n) | O(h) | 通用模板 | 需要状态标记 |
| 颜色标记 | O(n) | O(h) | 易于理解 | 额外状态 |
| Morris | O(n) | O(1) | 空间最优 | 实现复杂 |
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
3
0- 0
已为社区贡献7条内容
所有评论(0)