4.2 画图让抽象问题形象化

画图是在面试过程中应聘者用来帮助自己分析、推理的常用手段。很多面试题很抽象，不容易找到解决办法。这时不妨画出一些与题目相关的图形，借以辅助自己观察和思考。图形能使抽象的问题具体化、形象化，应聘者说不定通过几幅图形就能找到规律，从而找到问题的解决方案。

有不少与数据结构相关的问题，比如二叉树、二维数组、链表等问题，都可以采用画图的方法来分析。很多时候空想未必能想明白题目中隐含的规律和特点，随手画几幅图却能让我们轻易地找到窍门。比如在面试题27“二叉树的镜像”中，我们画几幅二叉树的图就能发现，求树的镜像的过程其实就是在遍历树的同时交换非叶节点的左、右子节点。在面试题29“顺时针打印矩阵”中，我们画图之后很容易就发现可以把矩阵分解成若干个圆圈，然后从外向内打印每个圆圈。面试的时候很多人都会在边界条件上犯错误（因为最后一圈可能退化而不是一个完整的圈），如果画几幅示意图，就能够很容易找到最后一圈退化的规律。对于面试题35“复杂链表的复制”，如果能够画出每一步操作时的指针操作，那么接下来写代码就会容易得多。

在面试的时候，应聘者需要向面试官解释自己的思路。对于复杂的问题，应聘者光用语言未必能够说得清楚。这时候可以画出几幅图形，一边看着图形一边讲解，面试官就能更加轻松地理解应聘者的思路。这对应聘者是有益的，因为面试官会觉得他具有很好的沟通交流能力。

面试题27：二叉树的镜像

题目：请完成一个函数，输入一棵二叉树，该函数输出它的镜像。二叉树节点的定义如下：

struct BinaryTreeNode

{

int m_nValue;

BinaryTreeNode* m_pLeft;

BinaryTreeNode* m_pRight;

};

树的镜像对很多人来说是一个新的概念，我们未必能够一下子想出求树的镜像的方法。为了能够形成直观的印象，我们可以自己画一棵二叉树，然后根据照镜子的经验画出它的镜像。如图4.1中右边的二叉树就是左边的树的镜像。

图4.1 两棵互为镜像的二叉树

仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根节点相同，但它们的左、右两个子节点交换了位置。因此，我们不妨先在树中交换根节点的两个子节点，就得到图4.2中的第二棵树。

交换根节点的两个子节点之后，我们注意到值为10、6的节点的子节点仍然保持不变，因此我们还需要交换这两个节点的左、右子节点。交换之后的结果分别是图4.2中的第三棵树和第四棵树。做完这两次交换之后，我们已经遍历完所有的非叶节点。此时变换之后的树刚好就是原始树的镜像。

图4.2 求二叉树镜像的过程

注：（a）交换根节点的左、右子树；（b）交换值为10的节点的左、右子节点；（c）交换值为6的节点的左、右子节点。

总结上面的过程，我们得出求一棵树的镜像的过程：先前序遍历这棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点。当交换完所有非叶节点的左、右子节点之后，就得到了树的镜像。

想清楚了这种思路，我们就可以动手写代码了。参考代码如下：

void MirrorRecursively (BinaryTreeNode *pNode)

{

if(pNode == nullptr)

return;

if(pNode->m_pLeft == nullptr && pNode->m_pRight == nullptr)

return;

BinaryTreeNode *pTemp = pNode->m_pLeft;

pNode->m_pLeft = pNode->m_pRight;

pNode->m_pRight = pTemp;

if(pNode->m_pLeft)

MirrorRecursively(pNode->m_pLeft);

if(pNode->m_pRight)

MirrorRecursively(pNode->m_pRight);

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/27_ MirrorOfBinaryTree

测试用例：

功能测试（普通的二叉树；二叉树的所有节点都没有左子树或者右子树；只有一个节点的二叉树）。

特殊输入测试（二叉树的根节点为nullptr指针）。

本题考点：

考查应聘者对二叉树的理解。本题实质上是利用树的遍历算法解决问题。

考查应聘者的思维能力。树的镜像是一个抽象的概念，应聘者需要在短时间内想清楚求镜像的步骤并转换为代码。应聘者可以通过画图把抽象的问题形象化，这有助于其快速找到解题思路。

本题扩展：

上面的代码是用递归实现的。如果要求用循环，则该如何实现？

面试题28：对称的二叉树

题目：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，在如图4.3所示的3棵二叉树中，第一棵二叉树是对称的，而另外两棵不是。

图4.3 3棵二叉树，其中第一棵二叉树是对称的，另外两棵不是

我们有3种不同的二叉树遍历算法，即前序遍历、中序遍历和后序遍历。在这3种遍历算法中，都是先遍历左子节点再遍历右子节点。我们是否可以定义一种遍历算法，先遍历右子节点再遍历左子节点？比如我们针对前序遍历定义一种对称的遍历算法，即先遍历父节点，再遍历它的右子节点，最后遍历它的左子节点。

如果用前序遍历算法遍历图4.3中的第一棵二叉树，则遍历序列是{8, 6, 5, 7, 6, 7, 5}。如果用我们定义的针对前序遍历的对称遍历算法，则得到的遍历序列是{8, 6, 5, 7, 6, 7, 5}。我们注意到这两个序列是一样的。

图4.3中第二棵二叉树的前序遍历序列为{8, 6, 5, 7, 9, 7, 5}，而相应的对称前序遍历序列为{8, 9, 5, 7, 6, 7, 5}。在这两个序列中，第二步和第五步是不一样的。

第三棵二叉树有些特殊，它所有节点的值都是一样的。它的前序遍历序列是{7, 7, 7, 7