s1.pop(); s2.push(curr); if (curr->left) s1.push(curr->left); if (curr->right) s1.push(curr->right); } while (!s2.empty()) { TreeNode* curr = s2.top(); s2.pop(); result.push_back(curr->val); } return result; } int main() { string preorder = "ABDGCEF"; // 先序序列 string inorder = "DGBAECF"; // 中序序列 TreeNode* root = buildTree(preorder, inorder); // 构建二叉树 vector<char> preorderResult = preorderTraversal(root); // 前序非递归遍历 vector<char> inorderResult = inorderTraversal(root); // 中序非递归遍历 vector<char> postorderResult = postorderTraversal(root); // 后序非递归遍历 // 输出三种遍历序列的结果 cout << "前序非递归遍历: "; for (size_t i = 0; i < preorderResult.size(); i++) { cout << preorderResult[i] << " "; } cout << endl; cout << "中序非递归遍历: "; for (size_t i = 0; i < inorderResult.size(); i++) { cout << inorderResult[i] << " "; } cout << endl; cout << "后序非递归遍历: "; for (size_t i = 0; i < postorderResult.size(); i++) { cout << postorderResult[i] << " "; } cout << endl; return 0; }

这是一个用 C++ 实现的二叉树构建和三种非递归遍历的代码。在这个代码中，先序遍历、中序遍历和后序遍历都采用非递归的方式实现。这个代码的具体实现过程如下：

1. 首先，根据给定的先序序列和中序序列构建二叉树。这里使用了递归的方式构建二叉树，具体实现可参考 LeetCode 题目 105。

2. 然后，分别实现三种非递归遍历方式。具体实现过程如下：

- 前序遍历：使用一个栈来保存遍历过的节点。首先将根节点入栈，然后循环执行以下操作，直到栈为空。从栈中弹出一个节点，将节点的值保存到结果数组中，然后将节点的右子节点和左子节点依次入栈。

- 中序遍历：使用一个栈来保存遍历过的节点。首先将根节点入栈，然后循环执行以下操作，直到栈为空。从栈中弹出一个节点，如果该节点有左子节点，则将左子节点入栈。如果该节点没有左子节点或者左子节点已经被访问过了，则将节点的值保存到结果数组中，然后将节点的右子节点入栈。

- 后序遍历：使用两个栈来保存遍历过的节点。首先将根节点入栈1，然后循环执行以下操作，直到栈1为空。从栈1中弹出一个节点，并将该节点入栈2。然后依次将该节点的左子节点和右子节点入栈1。最后，从栈2中依次弹出节点，并将节点的值保存到结果数组中。

3.最后，在 main 函数中分别调用三种非递归遍历函数，并输出遍历结果。

需要注意的是，这个代码中使用了自定义的 TreeNode 结构体来表示二叉树节点，其定义可能与 LeetCode 题目中的定义略有不同。

相关问题

用C语言在原来给定的exp7-2基础上，实现二叉树的中序遍历和后序遍历的递归和非递归算法。要求建立的二叉树如图所示

在C语言中，我们可以使用结构体表示二叉树节点，并分别编写递归和非递归的方式来实现二叉树的中序遍历和后序遍历。首先，我们需要定义一个二叉树节点的结构体：

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

接下来，我们分别实现中序遍历、后序遍历的递归版本：

// 中序遍历(递归)
void inorderTraversalRec(TreeNode* root) {
    if (root != NULL) {
        inorderTraversalRec(root->left);
        printf("%d ", root->val); // 先左后根
        inorderTraversalRec(root->right);
    }
}

// 后序遍历(递归)
void postorderTraversalRec(TreeNode* root) {
    if (root != NULL) {
        postorderTraversalRec(root->left);
        postorderTraversalRec(root->right);
        printf("%d ", root->val); // 先右后根
    }
}

然后是非递归版本，这里我们会使用栈来辅助：

// 中序遍历(非递归)
void inorderTraversalNonRec(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        printf("%d ", curr->val);
        curr = curr->right;
    }
}

// 后序遍历(非递归)
void postorderTraversalNonRec(TreeNode* root) {
    stack<TreeNode*> s1, s2;
    s1.push(root);
    TreeNode* curr = NULL;

    while (!s1.empty()) {
        curr = s1.top();
        s1.pop();

        if (curr->left == NULL && curr->right == NULL) {
            printf("%d ", curr->val);
            s2.push(curr);
        } else if (curr->right != NULL) {
            s1.push(curr->right);
        } else {
            s1.push(curr->left);
        }
    }

    while (!s2.empty()) {
        printf("%d ", s2.top()->val);
        s2.pop();
    }
}

注意：为了使用这些函数，你需要先构建一个像下面这样的二叉树：

TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 5;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 3;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 2;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 4;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 6;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->val = 7;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->right->val = 8;