剑指offer：二叉树的镜像

题目描述：

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如：

输入二叉树：

        8

      /   \

     6     10

    / \   /  \

   5   7 9   11

输出二叉树：

         8

       /   \

     10     6

    / \   /  \

   11   9 7    5

思路分析：

通过画图可以看出，将一棵二叉树的左右子树进行交换，就是这棵二叉树的镜像。构建一个递归函数，将每个节点的左右子树都交换一下即可。

代码实现：

1.递归实现：

class Solution {

public:

    void Mirror(TreeNode *pRoot) {

        if(pRoot == nullptr)

            return;

        TreeNode* temp = pRoot->left;

        pRoot->left = pRoot->right;

        pRoot->right = temp;

        Mirror(pRoot->left);

        Mirror(pRoot->right);

    }

};

2.非递归实现：

class Solution {

public:

    void Mirror(TreeNode *pRoot) {

        if(pRoot == nullptr)

            return;

        stack<TreeNode*> s;

        s.push(pRoot);

        while(!s.empty()){

            TreeNode* temp = s.top();

            s.pop();

            if(temp->left != nullptr || temp->right != nullptr){

                TreeNode* t = temp->left;

                temp->left = temp->right;

                temp->right = t;

            }

            if(temp->left != nullptr)

                s.push(temp->left);

            if(temp->right != nullptr)

                s.push(temp->right);

        }

    }

};

总结：

1.本题采用递归和非递归两种方法实现，具体看自己的喜好。

2.注意判断空指针的情况，遍历左右子树时都要判断是否为空。

3.本题思路简单，关键是多加练习，不断熟悉二叉树的遍历。