面试题19:二叉树的镜像

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

二叉树的节点定义如下:

1
2
3
4
5
6
7
8
struct BinaryTreeNode{
int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int data=int()):value(data),left(NULL),right(NULL)
{}
};


分析

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

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

1
2
3
4
5
6
7
8
9
void MirrorRecursively(BinaryTreeNode* root)
{
if(root==NULL)
return;
swap(root->left,root->right);
MirrorRecursively(root->left);
MirrorRecursively(root->right);
}

以上

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

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