例题-二叉树的镜像

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
比如:
源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11

镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5

原理

既然我们想获得二叉树的镜像,那么根节点的两边必然是反过来的啊。所以第一步我们交换左右子树。

这时我们发现交换后的左右子树的子节点还是保持原来的顺序,所以需要我们去交换左右子树自己的左右子树。

综上,我们的大问题已经逐步转化为了相同的子问题,第一步交换根节点的左右子树,之后交换左右子树自己的左右子树,这样的操作除了操作对象不同,但是操作步骤是一样,所以采用递归来做,我们用递归方式来递归交换各个左右子树。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class TreeNode 
{
public:
int data;
TreeNode* lchild = nullptr;
TreeNode* rchild = nullptr;
TreeNode(int data) :data(data) {};
~TreeNode() {};
};

class Tree
{
public:
TreeNode* Tree::Mirror(TreeNode* pRoot)
{ //镜像翻转二叉树
if (pRoot == nullptr)
return nullptr;
TreeNode* node1 = pRoot->lchild;
TreeNode* node2 = pRoot->rchild;
pRoot->lchild = Mirror(node2);
pRoot->rchild = Mirror(node1);
return pRoot;
}
};

输入为

1
[1,2,3,21,22,31,32]

输出为

1
[1,3,2,32,31,22,21]