后序遍历的顺序是左子树 → 右子树 → 根节点。相比前序和中序后序的非递归实现稍显复杂因为需要确保在访问根节点之前它的左右子树都已经处理完毕。这里介绍一种使用栈和辅助指针的解法通过标记已访问的节点来避免重复进入右子树。问题描述给定一棵二叉树的根节点root返回其节点值的后序遍历结果。例如输入[1,null,2,3]输出[3,2,1]。输入空树输出[]。思路分析后序遍历的非递归难点在于当从栈中弹出某个节点时无法直接判断该节点的右子树是否已经被访问过。因为如果右子树存在且未被访问当前节点还不能出栈需要先处理右子树。为了解决这个问题可以用一个指针prev记录上一次访问的节点。对于栈顶节点top如果top的右子树为空或者右子树已经访问过即top-right prev说明左右子树都已处理完毕可以访问top然后将其出栈并更新prev为top。否则说明右子树还未处理需要将当前指针cur指向top-right开始遍历右子树。整体流程与中序遍历类似先沿着左子树一路压栈然后根据右子树的情况决定是否访问当前节点。代码实现cppclass Solution { public: vectorint postorderTraversal(TreeNode* root) { stackTreeNode* st; vectorint result; TreeNode* prev nullptr; // 记录上一个访问的节点 TreeNode* cur root; while (cur ! nullptr || !st.empty()) { // 一直向左走将节点压栈 while (cur ! nullptr) { st.push(cur); cur cur-left; } TreeNode* top st.top(); // 取栈顶节点但不弹出 // 如果右子树为空或者右子树已经访问过则可以访问当前节点 if (top-right nullptr || top-right prev) { result.push_back(top-val); prev top; // 更新 prev 为当前节点 st.pop(); // 弹出当前节点 } else { // 否则先处理右子树 cur top-right; } } return result; } };代码解释cur指针负责遍历树初始指向根节点。prev指针记录上一次被访问的节点用于判断右子树是否已处理。外层while循环控制整体流程条件cur ! nullptr || !st.empty()确保当树非空或栈中还有节点时继续执行。第一个内层while循环沿着当前节点的左子树一直向下将沿途节点压栈。这模拟了递归先深入到左子树的过程。之后取出栈顶节点top注意此时并未弹出然后进行判断如果top的右子树为空那么显然左右子树都已处理左子树因为已经走到尽头实际上已经处理完毕可以直接访问top。如果top的右子树不为空但top-right prev说明右子树刚刚被访问完因为prev是上一个访问的节点此时也可以访问top。其他情况说明右子树还未处理需要将cur指向top-right进入右子树的遍历下一轮外层循环会先处理该右子树的左链。访问节点时将其值加入结果数组更新prev并弹出栈顶节点。复杂度分析时间复杂度O(n)每个节点恰好被压栈一次、弹栈一次且每个节点被检查若干次常数次总体线性时间。空间复杂度O(h)h 为树的高度。栈中最多同时存放一条从根到当前节点的路径上的节点。最坏情况下树退化为链表空间复杂度为 O(n)平均情况 O(logn)。注意事项与中序遍历不同后序遍历中栈顶节点不一定立即弹出需要根据右子树的状态决定。prev的更新时机很关键必须在节点真正被访问即值被记录之后才更新。这种解法利用了额外的指针来标记访问状态属于比较直观的解法。另一种常见技巧是使用两个栈或者修改节点结构如增加标志位但题目要求不能修改原树因此上述方法是合适的选择。总结后序遍历的非递归实现需要妥善处理右子树的访问时机。通过增加一个prev指针记录上一次访问的节点可以有效地判断当前节点的右子树是否已经处理完毕。这种方法代码清晰易于理解是面试和工程中的常用写法。掌握了它二叉树的三序遍历非递归实现就齐全了。