深入理解C++后序遍历（手把手教你实现二叉树后序遍历算法）

为什么需要后序遍历？

后序遍历常用于以下场景：

• 释放二叉树内存（先释放子节点，再释放父节点）
• 计算目录大小（先统计子目录，再汇总到父目录）
• 表达式树求值（操作数在前，运算符在后）

C++实现后序遍历

我们首先定义一个简单的二叉树节点结构：

struct TreeNode {    int val;    TreeNode* left;    TreeNode* right;        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};

方法一：递归实现（推荐初学者使用）

递归是最直观、最容易理解的实现方式。利用函数调用栈自动管理遍历过程。

#include <iostream>#include <vector>using namespace std;// 后序遍历递归函数void postorderTraversal(TreeNode* root, vector<int>& result) {    if (root == nullptr) {        return;    }        // 先遍历左子树    postorderTraversal(root->left, result);        // 再遍历右子树    postorderTraversal(root->right, result);        // 最后访问根节点    result.push_back(root->val);}// 封装接口vector<int> postorderTraversal(TreeNode* root) {    vector<int> result;    postorderTraversal(root, result);    return result;}

使用示例：

int main() {    // 构建如下二叉树：    //       1    //      / \    //     2   3    //    / \    //   4   5    TreeNode* root = new TreeNode(1);    root->left = new TreeNode(2);    root->right = new TreeNode(3);    root->left->left = new TreeNode(4);    root->left->right = new TreeNode(5);        vector<int> result = postorderTraversal(root);        cout << "后序遍历结果: ";    for (int val : result) {        cout << val << " ";    }    // 输出: 4 5 2 3 1        return 0;}

方法二：迭代实现（进阶）

虽然递归简洁，但在某些情况下（如树很深）可能导致栈溢出。此时可使用显式栈进行迭代实现。

#include <stack>#include <vector>vector<int> postorderTraversalIterative(TreeNode* root) {    vector<int> result;    if (!root) return result;        stack<TreeNode*> stk;    TreeNode* lastVisited = nullptr;        while (root || !stk.empty()) {        if (root) {            stk.push(root);            root = root->left;        } else {            TreeNode* peekNode = stk.top();            // 如果右子树存在且未被访问过            if (peekNode->right && lastVisited != peekNode->right) {                root = peekNode->right;            } else {                result.push_back(peekNode->val);                lastVisited = peekNode;                stk.pop();            }        }    }        return result;}

总结

通过本文，你已经掌握了C++后序遍历的基本原理和两种实现方式。对于初学者，建议先熟练掌握递归写法；当你对栈和指针有更深理解后，可以尝试迭代版本。

记住，后序遍历算法实现的关键在于“左右根”的访问顺序。多加练习，你就能轻松应对面试或实际开发中的相关问题！

希望这篇教程对你有所帮助。如果你喜欢，请分享给更多正在学习C++递归遍历的朋友！