答案是使用栈模拟递归实现中序遍历：从根节点开始，循环将左子节点入栈直至为空，然后弹出栈顶访问，并转向右子树，重复过程直至栈空且当前节点为空；时间复杂度O(n)，空间复杂度O(h)。
在C++中实现二叉树的中序遍历非递归方式，核心思路是使用栈来模拟递归过程。中序遍历的顺序是：左子树 → 根节点 → 右子树。由于不能依赖系统调用栈，我们需要手动管理访问路径。
基本思路
利用栈记录待访问的节点。从根节点开始，不断向左走，将经过的节点入栈。当左路到底后，弹出栈顶节点并访问，然后转向其右子树，重复此过程。
数据结构定义
先定义二叉树节点结构：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
非递归中序遍历实现
以下是完整的非递归中序遍历代码：
立即学习“C++免费学习笔记（深入）”；
void inorderTraversal(TreeNode* root) {
if (!root) return;
std::stack
TreeNode* curr = root;
while (curr || !stk.empty()) {
while (curr) {
stk.push(curr);
curr = curr->left;
}
curr = stk.top();
stk.pop();
std::cout val
curr = curr->right; // 转向右子树
}
}
关键点说明
• 循环条件：当前节点不为空或栈不为空，确保所有节点都被处理。
• 左路入栈：一直向左并将路径上节点压入栈，直到空节点。
• 访问与转向：弹出栈顶即为应访问的节点，之后进入其右子树。
• 避免重复访问：每次处理完一个节点后，将其置为右孩子，不会再次进入左子树。
基本上就这些。这个方法时间复杂度O(n)，空间复杂度最坏O(h)，h为树高。适合理解栈在树遍历中的作用，也常用于线索二叉树等场景的替代方案。
