C++二叉树后序遍历实现方法

方法二：迭代实现（使用栈）

一种常见做法是使用一个指针记录上一个访问的节点，避免重复进入右子树：

void postorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) return;
std::stack<TreeNode*> stack;
TreeNode* lastVisited = nullptr;
TreeNode* current = root;

while (current != nullptr || !stack.empty()) {
    if (current != nullptr) {
        stack.push(current);
        current = current->left;  // 一直向左走
    } else {
        TreeNode* peekNode = stack.top();
        // 如果右子树存在且未被访问过，进入右子树
        if (peekNode->right != nullptr && lastVisited != peekNode->right) {
            current = peekNode->right;
        } else {
            std::cout << peekNode->val << " ";
            lastVisited = stack.top();
            stack.pop();
        }
    }
}
}

测试示例

你可以这样测试上述代码：

int main() {
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);
std::cout << "后序遍历结果: ";
postorderTraversalRecursive(root); // 输出: 3 2 1
std::cout << std::endl;

return 0;
}

基本上就这些。递归写起来快，迭代更安全。根据实际需求选择合适的方法即可。