深度优先搜索的后序遍历

深度优先搜索的后序遍历指的是在深度优先搜索过程中，每个节点被访问的时间顺序。具体来说，后序遍历是在深度优先搜索中，当一个节点的所有子节点都被访问完毕后，才对这个节点进行访问。

深度优先搜索的后序遍历可以用递归或者栈实现。如果使用递归实现深度优先搜索，那么后序遍历的顺序就是在递归函数的最后一行打印当前节点的值。如果使用栈实现深度优先搜索，那么后序遍历的顺序就是在弹出栈顶元素时打印当前节点的值。

以二叉树为例，深度优先搜索的后序遍历算法可以写成如下形式：

// 使用递归实现深度优先搜索后序遍历
void postOrderTraversal(Node* root) {
    if (root == nullptr) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    std::cout << root->val << " ";
}

// 使用栈实现深度优先搜索后序遍历
void postOrderTraversal(Node* root) {
    std::stack<Node*> s;
    Node* cur = root;
    Node* last = nullptr;  // 记录上一个访问的节点
    while (cur != nullptr || !s.empty()) {
        // 先遍历左子树
        while (cur != nullptr) {
            s.push(cur);
            cur = cur->left;
        }
        // 取出栈顶元素
        cur = s.top();
        s.pop();
        // 如果当前节点的右子树为空，或者右子树已经被访问过了，就可以访问当前节点
        if (cur->right == nullptr || cur->right == last) {
            std::cout << cur->val << " ";
            last = cur;
            cur = nullptr;
        } else {
            // 否则，遍历右子树
            s.push(cur);
            cur = cur->right;
        }
    }
}

以上代码分别使用递归和栈实现了深度优先搜索的后序遍历。其中，栈实现的算法使用了一个辅助指针 last 来记录上一个被访问的节点，以便在访问当前节点之前判断其右子树是否已经被访问过。