如何在使用迭代推到 std::stack 时更新指针？

Question

情况如下：

Given a pointer to the root of a binary search tree(of integers) root and an integer data, perform the rotate function (predefined) on all the ancestral nodes of the node containing data using iterative method. For simplicity, assume data exists and always occurs on the leaf nodes.

rotate函数通过引用传递指针如下：

struct Node
{
    Node *left;
    int data;
    Node *right;
};

void rotate(Node* &root); // performs some rotation on the root and reflects the change.

void search(Node* &root, int data)
{
    stack<Node*> s;
    while(root->data!=data)
    {
        s.push(root);
        if(data<root->data)
            root=root->left;
        else
            root=root->right;
    }

    while(!s.empty())
    {
        rotate(s.top()); // does not reflect changes to root
        s.pop();
    }
}

迭代版本需要使用堆栈。 std::stack::push() 函数按值压入指针。因此，在弹出祖先指针时，我会反映堆栈中的变化。

针对这种情况最好的解决方法是什么？

Answer 1

这解决了我的问题。

void search(Node* &root, int data)
{   
    if(root->data==data)
        return;

    stack<Node**> s;
    while(root->data!=data)
    {
        if(data<root->data)
        {
            s.push(&root->left);
            root=root->left;
        }
        else
        {
            s.push(&root->right);
            root=root->right;
        }
    }
    s.pop(); // to avoid leaf
    while(!s.empty())
    {
        rotate(*s.top())
        s.pop();
    }
    rotate(root);
}