c++ - 即使修改后，堆栈的顶部元素仍保持不变
问题描述
我正在尝试在函数 preorderTraversal 中修改堆栈 stk 的顶部元素的状态字段，但是该字段似乎不会随时更改为 2 并且一直在 0 和 1 之间切换。谢谢你。
这就是算法应该如何工作 -
如果栈顶元素的状态为 0 ，则在欧拉遍历（前序）中第一次访问节点 如果栈顶元素的状态为 1 ，则第二次访问节点在欧拉遍历中（有序） 如果栈顶元素的状态为 2 ，则在欧拉遍历（后序）中第三次访问节点。
我通过修改堆栈顶部的状态字段并相应地在向量中插入树的前序、中序和后序来跟踪状态。
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class pairr
{
public:
TreeNode *node;
int status;
pairr(TreeNode *root, int status)
{
this->node = root;
this->status = status;
}
};
vector<int> preorderTraversal(TreeNode *root)
{
stack<pairr> stk;
vector<vector<int>> ans(3, vector<int>()); //ans[0 to 2] stores pre , in and postorder respectively .
stk.push(pairr(root, 0));
while (stk.empty() != true)
{
pairr temp = stk.top();
if (temp.status == 0) //if status is 0 ,in Euler traversal node is visited for the first time , so increase status to 1(preorder)
{
if (temp.node != NULL)
{
ans[0].push_back(temp.node->val);
if (temp.node->left)
{
stk.push(pairr(temp.node->left, 0));
}
}
temp.status += 1;
}
else if (temp.status == 1) //if status is 1 , in Euler traversal node is visited for the second time, so increase status to 2(Inorder)
{
if (temp.node != NULL)
{
ans[1].push_back(temp.node->val);
if (temp.node->right)
{
stk.push(pairr(temp.node->right, 0));
}
}
temp.status = 2;
}
else //if status is 2 , in Euler traversal node is visited for the third time, so add to vector and pop (Post order)
{
if (temp.node != NULL)
ans[2].push_back(temp.node->val);
stk.pop();
}
}
return ans[0];
}