答案是：C++中二叉树后序遍历有递归和迭代两种方法，顺序为左→右→根，递归简洁但可能栈溢出，迭代用栈模拟，适合深树。
在C++中实现二叉树的后序遍历，主要有两种方法：递归和迭代。后序遍历的顺序是“左子树 → 右子树 → 根节点”，适合用于释放树节点或计算表达式树等场景。
定义二叉树节点结构
在开始前，先定义一个基本的二叉树节点结构：
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
方法一：递归实现
递归是最直观的方式，按照“左→右→根”的顺序访问节点。
void postorderTraversalRecursive(TreeNode* root) {
if (root == nullptr) return;
postorderTraversalRecursive(root->left); // 遍历左子树
postorderTraversalRecursive(root->right); // 遍历右子树
std::cout << root->val << " "; // 访问根节点
}
优点是代码简洁易懂，缺点是在树很深时可能引发栈溢出。方法二：迭代实现（使用栈）
迭代法用显式栈模拟递归过程。关键点是判断节点是否已经处理过右子树。一种常见做法是使用一个指针记录上一个访问的节点，避免重复进入右子树：
void postorderTraversalIterative(TreeNode* root) {
if (root == nullptr) return;
std::stack stack;
TreeNode* lastVisited = nullptr;
TreeNode* current = root;
while (current != nullptr || !stack.empty()) {
if (current != nullptr) {
stack.push(current);
current = current->left; // 一直向左走
} else {
TreeNode* peekNode = stack.top();
// 如果右子树存在且未被访问过，进入右子树
if (peekNode->right != nullptr && lastVisited != peekNode->right) {
current = peekNode->right;
} else {
std::cout << peekNode->val << " ";
lastVisited = stack.top();
stack.pop();
}
}
}
}
这种方法空间复杂度为O(h)，h为树的高度，适合深度较大的树。测试示例
你可以这样测试上述代码：
int main() {
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
std::cout << "后序遍历结果: ";
postorderTraversalRecursive(root); // 输出: 3 2 1
std::cout << std::endl;
return 0;
}
基本上就这些。递归写起来快，迭代更安全。根据实际需求选择合适的方法即可。
立即学习“C++免费学习笔记（深入）”；
