求二叉树的镜像

就是对二叉树及其子树,交换左右子树。

这种就是先序遍历的变种。

递归版本:

void mirror(struct Node* root)
{
    if(root==NULL)
    {
        return ;
    }
    swap(&root->left, &root->right);
    mirror(root->left);
    mirror(root->right);
    return ;
}

所以非递归可以用栈轻松模拟:

void mirror(struct Node* root)
{
    stack<Node*> stk;
    stk.push_back(root);
    while(!stk.empty())
    {
        Node* ptr = stk.pop();
        if(ptr==NULL)
        {
            continue;
        }
        swap(&root->left, *root->right);
        stk.push_back(root->left);
        stk.push_back(root->right);
    }
    return ;
}

 

Leave a Reply

Your email address will not be published.