以二叉链表作存储结构，试编写前序、中序、后序遍历二叉树的算法。不用递归

以二叉链表作为二叉树的存储结构，我们可以分别设计非递归的前序、中序和后序遍历算法。这里以C++风格的代码为例：

1. **前序遍历（根-左-右）**:

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    Stack<TreeNode*> stack;
    stack.push(root);
    
    while (!stack.empty()) {
        TreeNode* node = stack.top();
        cout << node->val << " "; // 访问节点值
        stack.pop(); // 出栈当前节点

        if (node->right) {
            stack.push(node->right); // 先处理右子树
        }
        if (node->left) {
            stack.push(node->left); // 再处理左子树
        }
    }
}

2. **中序遍历（左-根-右）**:

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    Stack<TreeNode*> stack;
    TreeNode* cur = root;

    while (cur != nullptr || !stack.empty()) {
        while (cur != nullptr) {
            stack.push(cur);
            cur = cur->left;
        }
        cur = stack.top();
        stack.pop();
        cout << cur->val << " "; // 访问节点值
        cur = cur->right;
    }
}

3. **后序遍历（左-右-根）**:

void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    Stack<TreeNode*> stack1, stack2; // 两个栈用于辅助
    stack1.push(root);

    while (!stack1.empty()) {
        TreeNode* node = stack1.top();
        stack1.pop();

        stack2.push(node); // 将节点放入第二个栈，然后清空当前节点的左右子树

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

    while (!stack2.empty()) {
        cout << stack2.top()->val << " "; // 从第二个栈弹出并访问节点值
        stack2.pop();
    }
}