我想要的是非递归算法

对于非递归遍历二叉树，我们可以使用栈来实现。这是因为栈的特性恰好符合这种遍历方式的需求——先进后出。以下是三种非递归遍历的栈实现版本：

1. **前序遍历（非递归）**：

void preorderNonRecursive(TreeNode* root) {
    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* curr = s.top();
        s.pop();

        if (curr) {
            cout << curr->val << " "; // 访问当前节点
            s.push(curr->right); // 先右后左
            s.push(curr->left);
        }
    }
}

2. **中序遍历（非递归）**：

void inorderNonRecursive(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr || !s.empty()) {
        while (curr) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top(); // 出栈并访问当前节点
        s.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}

3. **后序遍历（非递归）**：

void postorderNonRecursive(TreeNode* root) {
    stack<TreeNode*> s1, s2; // 第一个栈保存待处理节点，第二个栈用于辅助
    s1.push(root);

    while (!s1.empty()) {
        TreeNode* curr = s1.top();
        s1.pop();
        
        s2.push(curr); // 将节点入第二个栈
        
        if (curr->left) s1.push(curr->left);
        if (curr->right) s1.push(curr->right);
    }

    while (!s2.empty()) {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

这些非递归遍历方法利用了栈的数据结构，避免了直接的函数嵌套，使得代码更易于理解和维护。