二叉树的镜像

题目：

操作给定的二叉树，将其变换为源二叉树的镜像。

方法一：递归

当交换节点左右孩子的指针的时候，不仅仅是交换了两个数，左节点的子孙换到二叉树的右侧，右节点的子孙换到二叉树的左侧；

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) 
    {
        if(pRoot==NULL)
            return;
        swap(pRoot->left,pRoot->right);
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};

方法二：队列的非递归实现

用中序遍历的方法交换二叉树的左右节点

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) 
    {
        if(pRoot==NULL)
            return;
        queue<TreeNode*>rel;
        rel.push(pRoot);
        while(!rel.empty())
        {
            TreeNode*front=rel.front();
            rel.pop();
            if(front->left!=NULL)
                rel.push(front->left);
            if(front->right!=NULL)
                rel.push(front->right);
            swap(front->left,front->right);
        }
    }
};

方法三：栈的非递归实现

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) 
    {
        if(pRoot==NULL)
            return;
        stack<TreeNode*>rel;
        rel.push(pRoot);
        while(!rel.empty())
        {
            TreeNode*top=rel.top();
            rel.pop();
            if(top->left!=NULL)
                rel.push(top->left);
            if(top->right!=NULL)
                rel.push(top->right);
            swap(top->left,top->right);
        }
    }
};

方法四：

非递归, 层次遍历+swap

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) 
    {
        if (!pRoot) 
            return;
        vector<TreeNode*> rel;
        rel.push_back(pRoot);
        while (!rel.empty())                //每次循环处理一层元素
        {
            vector<TreeNode*> tmp;
            for (auto &i : rel)             //将一层元素的所有孩子交换
            {
                swap(i->left, i->right);
                if (i->left)
                    tmp.push_back(i->left);
                if (i->right)
                    tmp.push_back(i->right);
            }
            rel.swap(tmp);                  //交换两个容器的元素
        }
    }
};