面试题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上:点我前往