c++中如何实现二叉树后序遍历非递归_c++二叉树后序非递归遍历方法

stack<TreeNode*> stk;
TreeNode* last = nullptr;        // 记录上一个访问的节点
TreeNode* curr = root;

while (curr || !stk.empty()) {
    // 一路向左入栈
    while (curr) {
        stk.push(curr);
        curr = curr->left;
    }

    // 取栈顶，不弹出
    curr = stk.top();

    // 如果右子树为空，或右子树已访问过
    if (!curr->right || curr->right == last) {
        cout << curr->val << " ";
        stk.pop();
        last = curr;           // 更新最后访问节点
        curr = nullptr;        // 避免重复进入左子树
    } else {
        curr = curr->right;    // 进入右子树
    }
}

<H3>双栈法（易于理解）</H3>
<p>另一种方法是使用两个栈：第一个栈按“根→右→左”的顺序压入节点，第二个栈用于反转输出顺序，最终得到“左→右→根”。</p>
<font color="#000000">
<ul>
  <li>先将根入栈1</li>
  <li>每次从栈1弹出节点，压入栈2，并依次将左、右孩子压入栈1</li>
  <li>最后依次弹出栈2，即为后序结果</li>
</ul>
</font>

<p>代码示例：</p>
```cpp
void postorderTwoStacks(TreeNode* root) {
    if (!root) return;

    stack<TreeNode*> stk1, stk2;
    stk1.push(root);

    while (!stk1.empty()) {
        TreeNode* node = stk1.top(); stk1.pop();
        stk2.push(node);

        if (node->left)  stk1.push(node->left);
        if (node->right) stk1.push(node->right);
    }

    // 输出栈2
    while (!stk2.empty()) {
        cout << stk2.top()->val << " ";
        stk2.pop();
    }
}