使用C++完成二叉树的前中后序遍历，不使用递归算法

在C++中，不使用递归算法实现二叉树的前序、中序和后序遍历通常会采用栈的数据结构。以下是这三种遍历方法的基本思路：

1. **前序遍历（Preorder Traversal）**:
- 先访问根节点（根->左->右）
- 可以使用一个栈来保存节点，首先将根节点入栈，然后进入循环：
- 弹出栈顶元素，访问它；
- 如果该元素有右孩子，将其右孩子入栈；
- 如果该元素有左孩子，将其左孩子入栈。

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

        // 非空右子节点和左子节点的顺序相反
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
}

2. **中序遍历（Inorder Traversal）**:
- 先访问左子树（左->根->右）
- 和前序类似，只是访问根节点的位置不同：
- 将左子树的所有节点都压入栈，直到遇到第一个非叶子节点；
- 访问这个节点，然后处理右子树。

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur = root;

    while (cur || !s.empty()) {
        // 左子树为空时，开始处理右子树
        while (cur) {
            s.push(cur);
            cur = cur->left;
        }

        cur = s.top(); // 出栈并访问当前节点
        s.pop();
        cout << cur->val << " "; // 打印节点值

        cur = cur->right; // 转向右子树
    }
}

3. **后序遍历（Postorder Traversal）**:
- 先访问左子树和右子树（左->右->根）
- 这里需要两个栈，一个用于存储节点，另一个临时存储待访问的节点：
- 当左右子树都处理完毕后，才访问当前节点。
- 使用一个辅助栈保存待访问的节点（左->根->右），最后弹出的是根节点。

void postorderTraversal(TreeNode* root) {
    stack<TreeNode*> s1, s2; // 主栈s1用于保存节点，辅助栈s2暂存节点
    s2.push(root);

    while (!s2.empty() || !s1.empty()) {
        if (!s1.empty() && !s2.empty() && s1.top()->right == s2.top()) {
            // 如果主栈的节点右子节点就是辅助栈的顶部，先访问这个节点
            TreeNode* node = s1.top();
            s1.pop();
            cout << node->val << " ";
            if (node->left != NULL) s2.push(node->left); // 把左子节点推到辅助栈
        } else {
            // 否则，先把当前节点的右子节点推进主栈
            TreeNode* node = s2.top();
            s2.pop();
            if (node->right) s1.push(node->right);
        }
    }
}