二叉树后序遍历c++代码

<think>好的，用户想要了解二叉树后序遍历的C++代码。我需要先回忆后序遍历的定义，即左-右-根的访问顺序。然后，考虑如何用代码实现，通常有递归和迭代两种方法。 首先，递归方法比较直接，先处理左子树，再处理右子树，最后访问根节点。但用户可能需要详细的代码示例，包括结构体定义和主函数调用。要注意代码的正确性，比如指针是否为nullptr的判断。 然后是迭代方法，这稍微复杂一些。需要用到栈来模拟递归的过程。记得后序遍历的迭代版本可能需要标记节点是否被访问过，或者利用前序的逆序。比如，可以用两个栈，一个用于处理节点，另一个用于反转结果。或者，使用一个栈，记录上一个访问的节点，来确定右子树是否处理完毕。 用户可能需要了解两种方法的优缺点。递归虽然简洁，但可能有栈溢出的风险；迭代更可控，但代码复杂一些。需要确保示例代码没有错误，比如指针操作是否正确，循环条件是否恰当。 另外，可能需要解释后序遍历的应用场景，比如释放二叉树内存，或者某些计算比如表达式的后缀表示。不过用户主要问的是代码实现，这部分可以简要提及。 还要检查代码是否符合C++标准，比如使用struct定义节点，是否有必要的头文件，比如iostream和stack。在示例中，是否创建了一个示例二叉树，并正确调用遍历函数，输出结果是否正确。 最后，确保回答结构清晰，分步骤说明递归和迭代的实现，给出代码示例，并解释关键部分。可能还需要比较两种方法的时间空间复杂度，都是O(n)，但递归的栈深度可能更大。</think>二叉树后序遍历遵循“左子树 → 右子树 → 根节点”的访问顺序。以下是C++代码实现及分步解析： --- ### 一、递归实现（最简方法） ```cpp #include <iostream> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void postorderTraversal(TreeNode* root) { if (root == nullptr) return; postorderTraversal(root->left); // 先遍历左子树 postorderTraversal(root->right); // 再遍历右子树 cout << root->val << " "; // 最后访问根节点 } // 示例用法 int main() { 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); postorderTraversal(root); // 输出：4 5 2 3 1 return 0; } ``` --- ### 二、迭代实现（显式栈模拟） ```cpp #include <iostream> #include <stack> using namespace std; void postorderTraversalIterative(TreeNode* root) { if (root == nullptr) return; stack<TreeNode*> stk; TreeNode* lastVisited = nullptr; while (root != nullptr || !stk.empty()) { // 深入左子树 while (root != nullptr) { stk.push(root); root = root->left; } TreeNode* top = stk.top(); // 若右子树存在且未被访问 if (top->right != nullptr && top->right != lastVisited) { root = top->right; } else { cout << top->val << " "; // 访问节点 lastVisited = top; stk.pop(); } } } ``` --- ### 三、方法对比 | 方法 | 时间复杂度 | 空间复杂度 | 特点 | |----------|------------|------------|--------------------------| | 递归 | $O(n)$ | $O(h)$ | 代码简洁，但栈深度受限 | | 迭代 | $O(n)$ | $O(n)$ | 可控性更强，适合大数据量 | --- ### 四、关键点解析 1. **递归终止条件**：当节点为`nullptr`时返回 2. **迭代核心逻辑**： - 使用栈模拟递归调用 - `lastVisited`标记最近访问的节点，避免重复处理右子树 3. **访问时机**：必须确保左右子树均处理完毕后才访问根节点 --- 实际应用中，后序遍历常用于： - 释放二叉树内存（先释放子节点再释放父节点） - 计算目录大小（先统计子目录再汇总父目录） - 表达式求值（后缀表达式）