面试题19：二叉树的镜像

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

二叉树的节点定义如下：

struct BinaryTreeNode{
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int data=int()):value(data),left(NULL),right(NULL)
    {}
};

分析

首先要弄明白什么是二叉树的镜像？镜像就是将二叉树的所有节点的左右指针交换后得到的二叉树。

所以很容易分析出，要得到二叉树的镜像，需要交换它每个节点的左右指针。我们依次遍历该二叉树的每一个节点，交换它的左右指针，然后再交换它的左右子树即可。因此可用递归来做：

void MirrorRecursively(BinaryTreeNode* root)
{
    if(root==NULL)
        return;
    swap(root->left,root->right);
    MirrorRecursively(root->left);
    MirrorRecursively(root->right);
}

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往