第4章 解决面试题的思路 4.1 面试官谈面试思路 “编码前讲自己的思路是一个考查指标。一个合格的应聘者应该在他做事之前明白自己要做的事情究竟是什么，以及该怎么做。一开始就编码的人员，除非后面表现非常优秀，否则很容易通不过。” ——殷焰（支付宝，高级安全测试工程师） “让应聘者给我讲具体的问题分析过程，经常会要求他证明。” ——张晓禹（百度，技术经理） “个人比较倾向于让应聘者在写代码之前解释他的思路。应聘者如果没有想清楚就动手本身就不是太好。应聘者可以采用举例子、画图等多种方式，解释清楚问题本身和问题解决方案是关键。” ——何幸杰（SAP，高级工程师） “对于比较复杂的算法和设计，一般来讲最好是在开始写代码前讲清楚思路和设计。” ——尧敏（淘宝，资深经理） “喜欢应聘者先讲清思路。如果觉察到方案的错误和漏洞，我会让他证明是否正确，主要是希望他能在分析的过程中发现这些错误和漏洞并加以改正。” ——陈黎明（微软，SDE II） “喜欢应聘者在写代码之前先讲思路，举例子和画图都是很好的方法。” ——田超（微软，SDE II） 4.2 画图让抽象问题形象化 画图是在面试过程中应聘者用来帮助自己分析、推理的常用手段。很多面试题很抽象，不是很容易找到解决办法。这时不妨画出一些与题目相关的图形，借以辅助自己观察和思考。图形能使抽象的问题具体化、形象化，应聘者说不定通过几个图形就能找到规律，从而找到问题的解决方案。 有不少与数据结构相关的问题，比如二叉树、二维数组、链表等问题，都可以采用画图的方法来分析。很多时候空想未必能想明白题目中隐含的规律和特点，随手画几张图却能让我们轻易找到窍门。比如在面试题19“二叉树的镜像”中我们画几张二叉树的图就能发现，求树的镜像的过程其实就是在遍历树的同时交换非叶结点的左右子结点。在面试题20“顺时针打印矩阵”中，我们画图之后很容易就发现可以把矩阵分解成若干个圆圈，然后从外向内打印每个圆圈。面试的时候很多人都会在边界条件上犯错误（因为最后一圈可能退化而不是一个完整的圈），如果画几张示意图，就能够很容易找到最后一圈退化的规律。对于面试题26“复杂链表的复制”，如果能够画出每一步操作时的指针操作，那接下来写代码就会容易得多。 在面试的时候应聘者需要向面试官解释自己的思路。对于复杂的问题，应聘者光用语言未必能够说得清楚。这个时候可以画出几个图形，一边看着图形一边讲解，面试官就能更加轻松地理解应聘者的思路。这对应聘者是有益的，因为面试官会觉得他有很好的沟通交流能力。 面试题19：二叉树的镜像 题目：请完成一个函数，输入一个二叉树，该函数输出它的镜像。二叉树结点的定义如下：  树的镜像对很多人来说是一个新的概念，我们未必能够一下子想出求树的镜像的方法。为了能够形成直观的印象，我们可以自己画一棵二叉树，然后根据照镜子的经验画出它的镜像。如图4.1中右边的二叉树就是左边的树的镜像。  图4.1 两棵互为镜像的二叉树 仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根结点相同，但它们的左右两个子结点交换了位置。因此我们不妨先在树中交换根结点的两个子结点，就得到图4.2中的第二棵树。 交换根结点的两个子结点之后，我们注意到值为10、6的结点的子结点仍然保持不变，因此我们还需要交换这两个结点的左右子结点。交换之后的结果分别是图4.2中的第三棵树和第四棵树。做完这两次交换之后，我们已经遍历完所有的非叶子结点。此时变换之后的树刚好就是原始树的镜像。  图4.2 求二叉树镜像的过程 注：（a）交换根结点的左右子树；（b）交换值为10的结点的左右子结点；（c）交换值为6的结点的左右子结点。 总结上面的过程，我们得出求一棵树的镜像的过程：我们先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子结点。当交换完所有非叶子结点的左右子结点之后，就得到了树的镜像。 想清楚了这个思路，我们就可以动手写代码了。参考代码如下：  源代码 本题完整的源代码详见19\_MirrorOfBinaryTree项目。 测试用例 ● 功能测试（普通的二叉树，二叉树的所有结点都没有左子树或者右子树，只有一个结点的二叉树）。 ● 特殊输入测试（二叉树的根结点为NULL指针）。 本题考点 ● 考查对二叉树的理解。本题实质上是利用树的遍历算法解决问题。 ● 考查应聘者的思维能力。树的镜像是一个抽象的概念，应聘者需要在短时间内想清楚求镜像的步骤并转化为代码。应聘者可以画图把抽象的问题形象化，这有助于其快速找到解题思路。 本题扩展 上面的代码是用递归实现的。如果要求用循环，该如何实现？ 面试题20：顺时针打印矩阵 题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。例如：如果输入如下矩阵：  则依次打印出数字1、2、3、4、8、12、16、15、14、13、9、5、6、7、11、10。 这道题完全没有涉及复杂的数据结构或者高级的算法，看起来是一个很简单的问题。但实际上解决这个问题，会在代码中包含多个循环，并且还需要判断多个边界条件。如果在把问题考虑得很清楚之前就开始写代码，不可避免会越写越混乱。因此解决这个问题的关键在于先要形成清晰的思路，并把复杂的问题分解成若干个简单的问题。 当我们遇到一个复杂问题的时候，可以用图形来帮助我们思考。由于是以从外圈到内圈的顺序依次打印，我们可以把矩阵想象成若干个圈，如图4.3所示。我们可以用一个循环来打印矩阵，每一次打印矩阵中的一个圈。  图4.3 把矩阵看成由若干个顺时针方向的圈组成 接下来分析循环结束的条件。假设这个矩阵的行数是rows，列数是columns。打印第一圈的左上角的坐标是（1,1），第二圈的左上角的坐标是（2,2），依此类推。我们注意到，左上角的坐标中行标和列标总是相同的，于是可以在矩阵中选取左上角为（start, start）的一圈作为我们分析的目标。 对一个5×5的矩阵而言，最后一圈只有一个数字，对应的坐标为（2,2）。我们发现5>2×2。对一个6×6的矩阵而言，最后一圈有4个数字，其左上角的坐标仍然为（2,2）。我们发现6>2×2依然成立。于是我们可以得出，让循环继续的条件是columns>startX×2并且rows>startY×2。所以我们可以用如下的循环来打印矩阵：  接着我们考虑如何打印一圈的功能，即如何实现PrintMatrixInCircle。如图4.3所示，我们可以把打印一圈分为四步：第一步从左到右打印一行，第二步从上到下打印一列，第三步从右到左打印一行，第四步从下到上打印一列。每一步我们根据起始坐标和终止坐标用一个循环就能打印出一行或者一列。 不过值得注意的是，最后一圈有可能退化成只有一行、只有一列，甚至只有一个数字，因此打印这样的一圈就不再需要四步。图4.4是几个退化的例子，打印一圈分别只需要三步、两步甚至只有一步。    图4.4 打印矩阵最里面一圈可能只需要三步、两步甚至一步 因此我们要仔细分析打印时每一步的前提条件。第一步总是需要的，因为打印一圈至少有一步。如果只有一行，那么就不用第二步了。也就是需要第二步的前提条件是终止行号大于起始行号。需要第三步打印的前提条件是圈内至少有两行两列，也就是说除了要求终止行号大于起始行号之外，还要求终止列号大于起始列号。同理，需要打印第四步的前提条件是至少有三行两列，因此要求终止行号比起始行号至少大2，同时终止列号大于起始列号。 通过上述的分析，我们就可以写出如下代码：  源代码： 本题完整的源代码详见20\_PrintMatrix项目。 测试用例： 数组有多行多列、数组只有一行、数组中只有一列、数组中只有一行一列。 本题考点： 本题主要考查应聘者的思维能力。从外到内顺时针打印矩阵这个过程非常复杂，应聘者如何能很快地找出其规律并写出完整的代码，是解决这道题的关键。当问题比较抽象不容易理解时，可以试着画几个图形帮助理解，这样往往能更快地找到思路。 4.3 举例让抽象问题具体化 和上一节画图的方法一样，我们也可以借助举例模拟的方法来思考分析复杂的问题。当一眼看不出问题中隐藏的规律的时候，我们可以试着用一两个具体的例子模拟操作的过程，这样说不定就能通过具体的例子找到抽象的规律。比如面试题22“栈的压入、弹出序列”，很多人都不能立即找到栈的压入和弹出规律。这时我们可以仔细分析一两个序列，一步一步模拟压入、弹出的操作，并从中总结出隐含的规律。面试题24“二叉搜索树的后序遍历序列”也类似，我们同样可以通过一两个具体的序列找到后续遍历的规律。 具体的例子也可以帮助我们向面试官解释算法思路。算法通常是很抽象的，用语言不容易表述得很清楚，我们可以考虑举出一两个具体的例子，告诉面试官我们的算法是怎么一步步处理这个例子的。例如在面试题21“包含min函数的栈”中，我们可以举例模拟压栈和弹出几个数字，分析每次操作之后数据栈、辅助栈和最小值各是什么。这样解释之后，面试官就能很清晰地理解我们的思路，同时他也会觉得我们有很好的沟通能力，能把复杂的问题用很简单的方式说清楚。 具体的例子还能帮助我们确保代码的质量。在面试中写完代码之后，应该先检查一遍，确保没有问题再交给面试官。怎么检查呢？我们可以运行几个测试用例。在分析问题的时候采用的例子就是测试用例。我们可以把这些例子当做测试用例，在心里模拟运行，看每一步操作之后的结果和我们预期的是不是一样。如果每一步的结果都和事先预计的一致，那我们就能确保代码的正确性了。 面试题21：包含min函数的栈 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O（1）。 看到这个问题，我们的第一反应可能是每次压入一个新元素进栈时，将栈里的所有元素排序，让最小的元素位于栈顶，这样就能在O（1）时间得到最小元素了。但这种思路不能保证最后压入栈的元素能够最先出栈，因此这个数据结构已经不是栈了。 我们接着想到在栈里添加一个成员变量存放最小的元素。每次压入一个新元素进栈的时候，如果该元素比当前最小的元素还要小，则更新最小元素。面试官听到这种思路之后就会问：如果当前最小的元素被弹出栈了，如何得到下一个最小的元素呢？ 分析到这里我们发现仅仅添加一个成员变量存放最小元素是不够的，也就是说当最小元素被弹出栈的时候，我们希望能够得到次小元素。因此在压入这个最小元素之前，我们要把次小元素保存起来。 是不是可以把每次的最小元素（之前的最小元素和新压入栈的元素两者的较小值）都保存起来放到另外一个辅助栈里呢？我们不妨举几个例子来分析一下把元素压入或者弹出栈的过程（如表4.1所示）。 表4.1 栈内压入3、4、2、1之后接连两次弹出栈顶数字再压入0时，数据栈、辅助栈和最小值的状态  （续表）  首先往空的数据栈里压入数字3，显然现在3是最小值，我们也把这个最小值压入辅助栈。接下来往数据栈里压入数字4。由于4大于之前的最小值，因此我们仍然往辅助栈里压入数字3。第三步继续往数据栈里压入数字2。由于2小于之前的最小值3，因此我们把最小值更新为2，并把2压入辅助栈。同样当压入数字1时，也要更新最小值，并把新的最小值1压入辅助栈。 从表4.1中我们可以看出，如果每次都把最小元素压入辅助栈，那么就能保证辅助栈的栈顶一直都是最小元素。当最小元素从数据栈内被弹出之后，同时弹出辅助栈的栈顶元素，此时辅助栈的新栈顶元素就是下一个最小值。比如第四步之后，栈内的最小元素是1。当第五步在数据栈内弹出1后，我们把辅助栈的栈顶弹出，辅助栈的栈顶元素2就是新的最小元素。接下来继续弹出数据栈和辅助栈的栈顶之后，数据栈还剩下3、4两个数字，3是最小值。此时位于辅助栈的栈顶数字正好也是3，的确是最小值。这说明我们的思路是正确的。 当我们想清楚上述过程之后，就可以写代码了。下面是3个关键函数push、pop和min的参考代码。在代码中，m\_data是数据栈，而m\_min是辅助栈。示例代码如下：  源代码： 本题完整的源代码详见21\_MinInStack项目。 测试用例： ● 新压入栈的数字比之前的最小值大。 ● 新压入栈的数字比之前的最小值小。 ● 弹出栈的数字不是最小的元素。 ● 弹出栈的数字是最小的元素。 本题考点： ● 考查分析复杂问题的思维能力。在面试的时候，很多应聘者都止步于添加一个变量保存最小元素的思路。其实只要举个例子多做几次入栈、出栈的操作就能看出问题，并想到也要把最小元素用另外的辅助栈保存。当我们面对一个抽象复杂的问题的时候，可以用几个具体的例子来找出规律。找到规律之后再解决问题，就容易多了。 ● 考查应聘者对栈的理解。 面试题22：栈的压入、弹出序列 题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但4、3、5、1、2就不可能是该压栈序列的弹出序列。 解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出数字。 以弹出序列4、5、3、2、1为例分析压栈和弹出的过程。第一个希望被弹出的数字是4，因此4需要先压入到辅助栈里面。压入栈的顺序由压栈序列确定了，也就是在把4压入进栈之前，数字1、2、3都需要先压入到栈里面。此时栈里包含4个数字，分别是1、2、3、4，其中4位于栈顶。把4弹出栈后，剩下的三个数字是1、2和3。接下来希望被弹出的数字是5，由于它不是栈顶数字，因此我们接着在第一个序列中把4以后数字压入辅助栈中，直到压入了数字5。这个时候5位于栈顶，就可以被弹出来了。接下来希望被弹出的三个数字依次是3、2和1。由于每次操作前它们都位于栈顶，因此直接弹出即可。表4.2总结了本例中入栈和出栈的步骤。 表4.2 压栈序列为1、2、3、4、5，弹出序列4、5、3、2、1对应的压栈和弹出过程  接下来再分析弹出序列4、3、5、1、2。第一个弹出的数字4的情况和前面一样。把4弹出之后，3位于栈顶，可以直接弹出。接下来希望弹出的数字是5，由于5不是栈顶数字，到压栈序列里把没有压栈的数字压入辅助栈，直至遇到数字5。把数字5压入栈之后，5就位于栈顶了，可以弹出。此时栈内有两个数字1和2，其中2位于栈顶。由于接下来需要弹出的数字是1，但1不在栈顶，我们需要从压栈序列中尚未压入栈的数字中去搜索这个数字。但此时压栈序列中所有数字都已经压入栈了。所以该序列不是序列1、2、3、4、5对应的弹出序列。表4.3总结了这个例子中压栈和弹出的过程。 表4.3 一个压入顺序为1、2、3、4、5的栈没有一个弹出序列为4、3、5、1、2  总结上述入栈、出栈的过程，我们可以找到判断一个序列是不是栈的弹出序列的规律：如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。 形成了清晰的思路之后，我们就可以动手写代码了。下面是一段参考代码：  源代码： 本题完整的源代码详见22\_StackPushPopOrder项目。 测试用例： ● 功能测试（输入的两个数组含有多个数字或者只有1个数字，第二个数组是或者不是第一个数组表示的压入序列对应的栈的弹出序列）。 ● 特殊输入测试（输入两个NULL指针）。 本题考点： ● 考查分析复杂问题的能力。刚听到这个面试题的时候，很多人可能都没有思路。这个时候，可以通过举一两个例子，一步步分析压栈、弹出的过程，从中找出规律。 ● 考查应聘者对栈的理解。 面试题23：从上往下打印二叉树 题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。例如输入图4.5中的二叉树，则依次打印出8、6、10、5、7、9、11。  图4.5 一棵二叉树，从上往下按层打印的顺序为8、6、10、5、7、9、11 二叉树结点的定义如下：  这道题实质是考查树的遍历算法，只是这种遍历不是我们熟悉的前序、中序或者后序遍历。由于我们不太熟悉这种按层遍历的方法，可能一下子也想不清楚遍历的过程。那面试的时候怎么办呢？我们不妨先分析一下打印图4.5中的二叉树的过程。 因为按层打印的顺序决定应该先打印根结点，所以我们从树的根结点开始分析。为了接下来能够打印值为8的结点的两个子结点，我们应该在遍历到该结点时把值为6和10的两个结点保存到一个容器里，现在容器内就有两个结点了。按照从左到右打印的要求，我们先取出值为6的结点。打印出值6之后把它的值分别为5和7的两个结点放入数据容器。此时数据容器中有三个结点，值分别为10、5和7。接下来我们从数据容器中取出值为10的结点。注意到值为10的结点比值为5、7的结点先放入容器，此时又比这两个结点先取出，这就是我们通常说的先入先出，因此不难看出这个数据容器应该是一个队列。由于值为5、7、9、11的结点都没有子结点，因此只要依次打印即可。整个打印过程如表4.4所示。 表4.4 按层打印图4.5中的二叉树的过程  通过上面具体例子的分析，我们可以找到从上到下打印二叉树的规律：每一次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。 既然我们已经确定数据容器是一个队列了，现在的问题就是如何实现队列。实际上我们无须自己动手实现，因为STL已经为我们实现了一个很好的deque（两端都可以进出的队列）。下面是用deque实现的参考代码：  本题考点： ● 考查思维能力。按层从上到下遍历二叉树，这对很多应聘者是个新概念，要在短时间内想明白遍历的过程不是一件容易的事情。应聘者通过具体的例子找出其中的规律并想到基于队列的算法，是解决这个问题的关键所在。 ● 考查应聘者对二叉树及队列的理解。 本题扩展： 如何广度优先遍历一个有向图？这同样也可以基于队列实现。树是图的一种特殊退化形式，从上到下按层遍历二叉树，从本质上来说就是广度优先遍历二叉树。 举一反三： 不管是广度优先遍历一个有向图还是一棵树，都要用到队列。第一步我们把起始结点（对树而言是根结点）放入队列中。接下来每一次从队列的头部取出一个结点，遍历这个结点之后把从它能到达的结点（对树而言是子结点）都依次放入队列。我们重复这个遍历过程，直到队列中的结点全部被遍历为止。 面试题24：二叉搜索树的后序遍历序列 题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。 例如输入数组{5,7,6,9,11,10,8}，则返回true，因为这个整数序列是图4.6二叉搜索树的后序遍历结果。如果输入的数组是{7,4,6,5}，由于没有哪棵二叉搜索树的后序遍历的结果是这个序列，因此返回false。  图4.6 后序遍历序列5、7、6、9、11、10、8对应的二叉搜索树 在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。 以数组{5,7,6,9,11,10,8}为例，后序遍历结果的最后一个数字8就是根结点的值。在这个数组中，前3个数字5、7和6都比8小，是值为8的结点的左子树结点；后3个数字9、11和10都比8大，是值为8的结点的右子树结点。 我们接下来用同样的方法确定与数组每一部分对应的子树的结构。这其实就是一个递归的过程。对于序列5、7、6，最后一个数字6是左子树的根结点的值。数字5比6小，是值为6的结点的左子结点，而7则是它的右子结点。同样，在序列9、11、10中，最后一个数字10是右子树的根结点，数字9比10小，是值为10的结点的左子结点，而11则是它的右子结点。 我们再来分析另一个整数数组{7,4,6,5}。后序遍历的最后一个数是根结点，因此根结点的值是5。由于第一个数字7大于5，因此在对应的二叉搜索树中，根结点上是没有左子树的，数字7、4和6都是右子树结点的值。但我们发现在右子树中有一个结点的值是4，比根结点的值5小，这违背了二叉搜索树的定义。因此不存在一棵二叉搜索树，它的后序遍历的结果是7、4、6、5。 找到了规律之后再写代码，就不是一件很困难的事情了。下面是参考代码：  源代码： 本题完整的源代码详见24\_SquenceOfBST项目。 测试用例： ● 功能测试（输入的后序遍历的序列对应一棵二叉树，包括完全二叉树、所有结点都没有左/右子树的二叉树、只有一个结点的二叉树；输入的后序遍历的序列没有对应一棵二叉树）。 ● 特殊输入测试（指向后序遍历序列的指针为NULL指针）。 本题考点： ● 考查分析复杂问题的思维能力。能否解决这道题的关键在于应聘者是否能找出后序遍历的规律。一旦找到规律了，用递归的代码编码相对而言就简单了。在面试的时候，应聘者可以从一两个例子入手，通过分析具体的例子寻找规律。 ● 考查对二叉树后序遍历的理解。 相关题目： 输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历的结果。这和前面问题的后序遍历很类似，只是在前序遍历得到的序列中，第一个数字是根结点的值。 举一反三： 如果面试题是要求处理一棵二叉树的遍历序列，我们可以先找到二叉树的根结点，再基于根结点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。本面试题是应用这个思路，面试题6“重建二叉树”也是应用这个思路。 面试题25：二叉树中和为某一值的路径 题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。二叉树结点的定义如下：  例如输入图4.7中二叉树和整数22，则打印出两条路径，第一条路径包含结点10、12，第二条路径包含结点10、5和7。  图4.7 二叉树中有两条和为22的路径：一条路径经过结点10、5、7，另一条路径经过结点10、12 一般的数据结构和算法的教材都没有介绍树的路径，因此对大多数应聘者而言，这是一个新概念，也就很难一下子想出完整的解题思路。这个时候我们可以试着从一两个具体的例子入手，找到规律。 以图4.7的二叉树作为例子来分析。由于路径是从根结点出发到叶结点，也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结点的。 按照前序遍历的顺序遍历图4.7中的二叉树，在访问结点10之后，就会访问结点5。从二叉树结点的定义可以看出，在本题的二叉树结点中没有指向父结点的指针，访问到结点5的时候，我们是不知道前面经过了哪些结点的，除非我们把经过的路径上的结点保存下来。每访问到一个结点的时候，我们都把当前的结点添加到路径中去。到达结点5时，路径中包含两个结点，它们的值分别是10和5。接下来遍历到结点4，我们把这个结点也添加到路径中。这个时候已经到达了叶结点，但路径上三个结点的值之和是19。这个和不等于输入的值22，因此不是符合要求的路径。 我们接着要遍历其他的结点。在遍历下一个结点之前，先要从结点4回到结点5，再去遍历结点5的右子结点7。值得注意的是，回到结点5的时候，由于结点4已经不在前往结点7的路径上了，我们需要把结点4从路径中删除。接下来访问到结点7的时候，再把该结点添加到路径中。此时路径中三个结点10、5、7之和刚好是22，是一条符合要求的路径。 我们最后要遍历的结点是12。在遍历这个结点之前，需要先经过结点5回到结点10。同样，每一次当从子结点回到父结点的时候，我们都需要在路径上删除子结点。最后从结点10到达结点12的时候，路径上的两个结点的值之和也是22，因此这也是一条符合条件的路径。 我们可以用表4.5总结上述的分析过程。 表4.5 遍历图4.7中的二叉树的过程  分析完前面具体的例子之后，我们就找到了一些规律。当用前序遍历的方式访问到某一结点时，我们把该结点添加到路径上，并累加该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是从根结点到父结点的路径。我们不难看出保存路径的数据结构实际上是一个栈，因为路径要与递归调用状态一致，而递归调用的本质就是一个压栈和出栈的过程。 形成了清晰的思路之后，就可以动手写代码了。下面是一段参考代码：  在前面的代码中，我们用标准模板库中的vector实现了一个栈来保存路径，每一次都用push\_back在路径的末尾添加结点，用pop\_back在路径的末尾删除结点，这样就保证了栈的先入后出的特性。这里没有直接用STL中的stack的原因是在stack中只能得到栈顶元素，而我们打印路径的时候需要得到路径上的所有结点，因此在代码实现的时候std::stack不是最好的选择。 源代码： 本题完整的源代码详见25\_PathInTree项目。 测试用例： ● 功能测试（二叉树中有一条、多条符合条件的路径，二叉树中没有符合条件的路径）。 ● 特殊输入测试（指向二叉树根结点的指针为NULL指针）。 本题考点： ● 考查分析复杂问题的思维能力。应聘者遇到这个问题的时候，如果一下子没有思路，不妨从一个具体的例子开始，一步步分析路径上包含哪些结点，这样就能找出其中的规律，从而想到解决方案。 ● 考查对二叉树的前序遍历的理解。 4.4 分解让复杂问题简单化 很多读者可能都知道“各个击破”的军事思想，这种思想的精髓是当敌我实力悬殊时，我们可以把强大的敌人分割开来，然后集中优势兵力打败被分割开来的小部分敌人。要一下子战胜总体很强大的敌人很困难，但战胜小股敌人就容易多了。同样，在面试中当我们遇到复杂的大问题的时候，如果能够先把大问题分解成若干个简单的小问题，然后再逐个解决这些小问题，那可能也会容易很多。 我们可以按照解决问题的步骤来分解复杂问题，每一步解决一个小问题。比如在面试题26“复杂链表的复制”中，我们将复杂链表复制的过程分解成三个步骤。在写代码的时候我们为每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。 在计算机领域有一类算法叫分治法，即“分而治之”，采用的就是各个击破的思想。我们把分解之后的小问题各个解决，然后把小问题的解决方案结合起来解决大问题。比如面试题27“二叉搜索树与双向链表”中，转换整个二叉树是一个大问题，我们先把这个大问题分解成转换左子树和右子树两个小问题，然后再把转换左右子树得到的链表和根结点链接起来，就解决了整个大问题。通常分治法思路都可以用递归的代码实现。 在面试题28“字符串的排列”中，我们把整个字符串分为两部分：第一个字符及它后面的所有字符。我们先拿第一个字符和后面的每个字符交换，交换之后再求后面所有字符的排列。整个字符串的排列是一个大问题，那么第一个字符之后的字符串的排列就是一个小问题。因此这实际上也是分治法的应用，可以用递归实现。 面试题26：复杂链表的复制 题目：请实现函数ComplexListNode\* Clone（ComplexListNode\* pHead），复制一个复杂链表。在复杂链表中，每个结点除了有一个m\_pNext指针指向下一个结点外，还有一个m\_pSibling 指向链表中的任意结点或者NULL。结点的C++定义如下：  图4.8是一个含有5个结点的复杂链表。图中实线箭头表示m\_pNext指针，虚线箭头表示m\_pSibling指针。为简单起见，指向NULL的指针没有画出。  图4.8 一个含有5个结点的复杂链表 注：在复杂链表的结点中，除了有指向下一结点的指针（实线箭头）外，还有指向任意结点的指针（虚线箭头）。 听到这个问题之后，很多应聘者的第一反应是把复制过程分成两步：第一步是复制原始链表上的每一个结点，并用m\_pNext链接起来；第二步是设置每个结点的m\_pSibling指针。假设原始链表中的某个结点N的m\_pSibling指向结点S，由于S的位置在链表中可能在N的前面也可能在N的后面，所以要定位S的位置需要从原始链表的头结点开始找。如果从原始链表的头结点开始沿着m\_pNext经过s步找到结点S，那么在复制链表上结点N’的m\_pSibling（记为S’）离复制链表的头结点的距离也是沿着m\_pNext指针s步。用这种办法我们就可以为复制链表上的每个结点设置m\_pSibling指针。 对于一个含有n个结点的链表，由于定位每个结点的m\_pSibling都需要从链表头结点开始经过O（n）步才能找到，因此这种方法的总时间复杂度是O（n2）。 由于上述方法的时间主要花费在定位结点的m\_pSibling上面，我们试着在这方面去做优化。我们还是分为两步：第一步仍然是复制原始链表上的每个结点N创建N’，然后把这些创建出来的结点用m\_pNext链接起来。同时我们把<N，N’>的配对信息放到一个哈希表中。第二步还是设置复制链表上每个结点的m\_pSibling。如果在原始链表中结点N的m\_pSibling指向结点S，那么在复制链表中，对应的N’应该指向S’。由于有了哈希表，我们可以用O（1）的时间根据S找到S’。 第二种方法相当于用空间换时间。对于有n个结点的链表我们需要一个大小为O（n）的哈希表，也就是说我们以O（n）的空间消耗把时间复杂度由O（n2）降低到O（n）。 接下来我们再换一种思路，在不用辅助空间的情况下实现O（n）的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点N创建对应的N’。这一次，我们把N’链接在N的后面。图4.8的链表经过这一步之后的结构，如图4.9所示。  图4.9 复制复杂链表的第一步 注：复制原始链表的任意结点N并创建新结点N'，再把N'链接到N的后面。 完成这一步的代码如下：  第二步设置复制出来的结点的m\_pSibling。假设原始链表上的N的m\_pSibling指向结点S，那么其对应复制出来的N’是N的m\_pNext指向的结点，同样S’也是S的m\_pNext指向的结点。设置m\_pSibling之后的链表如图4.10所示。  图4.10 复制复杂链表的第二步 注：如果原始链表上的结点N的m\_pSibling指向S，则它对应的复制结点N'的m\_pSibling指向S的下一结点S'。 下面是完成第二步的参考代码：  第三步把这个长链表拆分成两个链表：把奇数位置的结点用m\_pNext链接起来就是原始链表，把偶数位置的结点用m\_pNext链接起来就是复制出来的链表。图4.10中的链表拆分之后的两个链表如图4.11所示。   图4.11 复制复杂链表的第三步 注：把第二步得到的链表拆分成两个链表，奇数位置上的结点组成原始链表，偶数位置上的结点组成复制出来的链表。 要实现第三步的操作，也不是很难的事情。其对应的代码如下：  我们把上面三步合起来，就是复制链表的完整过程：  源代码： 本题完整的源代码详见26\_CopyComplexList项目。 测试用例： ● 功能测试（包括结点中的m\_pSibling指向结点自身，两个结点的m\_pSibling形成环状结构，链表中只有一个结点）。 ● 特殊输入测试（指向链表头结点的指针为NULL指针）。 本题考点： ● 考查应聘者对复杂问题的思维能力。本题中的复杂链表是一种不太常见的数据结构，而且复制这种链表的过程也较为复杂。我们把复杂链表的复制过程分解成三个步骤，同时把每一个步骤都用图形化的方式表示出来，这些方法都能帮助我们理清思路。写代码的时候，我们为每一个步骤定义一个子函数，最后在复制函数中先后调用者3个函数。有了这些清晰的思路之后再写代码，就容易多了。 ● 考查应聘者分析时间效率和空间效率的能力。当应聘者提出第一种和第二种思路的时候，面试官会提示此时在效率上还不是最优解。这个时候应聘者要能自己分析出这两种算法的时间复杂度和空间复杂度各是多少。 面试题27：二叉搜索树与双向链表 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。比如输入图4.12中左边的二叉搜索树，则输出转换之后的排序双向链表。  图4.12 一棵二叉搜索树及转换之后的排序双向链表 二叉树结点的定义如下：  在二叉树中，每个结点都有两个指向子结点的指针。在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。由于这两种结点的结构相似，同时二叉搜索树也是一种排序的数据结构，因此在理论上有可能实现二叉搜索树和排序的双向链表的转换。在搜索二叉树中，左子结点的值总是小于父结点的值，右子结点的值总是大于父结点的值。因此我们在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向后一个结点指针。接下来我们考虑该如何转换。 由于要求转换之后的链表是排好序的，我们可以中序遍历树中的每一个结点，这是因为中序遍历算法的特点是按照从小到大的顺序遍历二叉树的每一个结点。当遍历到根结点的时候，我们把树看成三部分：值为10的结点、根结点值为6的左子树、根结点值为14的右子树。根据排序链表的定义，值为10的结点将和它的左子树的最大一个结点（即值为8的结点）链接起来，同时它还将和右子树最小的结点（即值为12的结点）链接起来，如图4.13所示。  图4.13 把二叉搜索树看成三部分 注：根结点、左子树和右子树。在把左、右子树都转换成排序的双向链表之后再和根结点链接起来，整棵二叉搜索树也就转换成了排序的双向链表。 按照中序遍历的顺序，当我们遍历转换到根结点（值为10的结点）时，它的左子树已经转换成一个排序的链表了，并且处在链表中的最后一个结点是当前值最大的结点。我们把值为8的结点和根结点链接起来，此时链表中的最后一个结点就是10了。接着我们去遍历转换右子树，并把根结点和右子树中最小的结点链接起来。至于怎么去转换它的左子树和右子树，由于遍历和转换过程是一样的，我们很自然地想到可以用递归。 基于上述分析过程，我们可以写出如下代码：  在上面的代码中，我们用pLastNodeInList指向已经转换好的链表的最后一个结点（也是值最大的结点）。当我们遍历到值为10的结点的时候，它的左子树都已经转换好了，因此pLastNodeInList指向值为8的结点。接着把根结点链接到链表中之后，值为10的结点成了链表中的最后一个结点（新的值最大的结点），于是pLastNodeInList指向了这个值为10的结点。接下来把pLastNodeInList 作为参数传入函数递归遍历右子树。我们找到右子树中最左边的子结点（值为12的结点，在右子树中值最小），并把该结点和值为10的结点链接起来。 源代码： 本题完整的源代码详见27\_ConvertBinarySearchTree项目。 测试用例： ● 功能测试（输入的二叉树是完全二叉树，所有结点都没有左/右子树的二叉树，只有一个结点的二叉树）。 ● 特殊输入测试（指向二叉树根结点的指针为NULL指针）。 本题考点： ● 考查应聘者分析复杂问题的能力。无论是二叉树还是双向链表，都有很多指针。要实现这两种不同数据结构的转换，需要调整大量的指针，因此这个过程会很复杂。为了把这个复杂的问题分析清楚，我们可以把树分为三个部分：根结点、左子树和右子树，然后把左子树中最大的结点、根结点、右子树中最小的结点链接起来。至于如何把左子树和右子树内部的结点链接成链表，那和原来的问题的实质是一样的，因此可以递归解决。解决这个问题的关键在于把一个大的问题分解成几个小问题，并递归地解决小问题。 ● 考查对二叉树、双向链表的理解及编程能力。 面试题28：字符串的排列 题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。 如何求出几个字符的所有排列，很多人都不能一下子想出解决方案。那我们是不是可以考虑把这个复杂的问题分解成小的问题呢？比如，我们把一个字符串看成由两部分组成：第一部分为它的第一个字符，第二部分是后面的所有字符。在图4.14中，我们用两种不同的背景颜色区分字符串的两部分。 我们求整个字符串的排列，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。图4.14就是分别把第一个字符a和后面的b、c等字符交换的情形。首先固定第一个字符（如图4.14（a）所示），求后面所有字符的排列。这个时候我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换（如图4.14（b）所示）……  图4.14 求字符串的排列的过程 注：（a）把字符串分为两部分，一部分是字符串的第一个字符，另一部分是第一个字符以后的所有字符（有阴影背景的区域）。接下来我们求阴影部分的字符串的排列。（b）拿第一个字符和它后面的字符逐个交换。 分析到这里，我们就可以看出，这其实是很典型的递归思路，于是我们不难写出如下代码：  在函数Permutation（char\* pStr, char\* pBegin）中，指针pStr指向整个字符串的第一个字符，pBegin指向当前我们做排列操作的字符串的第一个字符。在每一次递归的时候，我们从pBegin向后扫描每一个字符（即指针pCh指向的字符）。在交换pBegin和pCh指向的字符之后，我们再对pBegin后面的字符串递归地做排列操作，直至pBegin指向字符串的末尾。 源代码： 本题完整的源代码详见28\_StringPermutation项目。 测试用例： ● 功能测试（输入的字符串中有1个或者多个字符）。 ● 特殊输入测试（输入的字符串的内容为空或者是NULL指针）。 本题考点： ● 考查思维能力。当整个问题看起来不能直接解决的时候，应聘者能否想到把字符串分成两部分，从而把大问题分解成小问题来解决，是能否顺利解决这个问题的关键。 ● 考查对递归的理解和编程能力。 本题扩展： 如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？还是输入三个字符a、b、c，则它们的组合有a、b、c、ab、ac、bc、abc。当交换字符串中的两个字符时，虽然能得到两个不同的排列，但却是同一个组合。比如ab和ba是不同的排列，但只算一个组合。 如果输入n个字符，则这n个字符能构成长度为1的组合、长度为2的组合、……、长度为n的组合。在求n个字符的长度为m（1≤m≤n）的组合的时候，我们把这n个字符分成两部分：第一个字符和其余的所有字符。如果组合里包含第一个字符，则下一步在剩余的字符里选取m－1个字符；如果组合里不包含第一个字符，则下一步在剩余的n－1个字符里选取m个字符。也就是说，我们可以把求n个字符组成长度为m的组合的问题分解成两个子问题，分别求n－1个字符串中长度为m－1的组合，以及求n－1个字符的长度为m的组合。这两个子问题都可以用递归的方式解决。 相关题目： 1．输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点上（如图4.15所示），使得正方体上三组相对的面上的4个顶点的和都相等。  图4.15 把8个数字放到正方体的8个顶点上 这相当于先得到a1、a2、a3、a4、a5、a6、a7和a8这8个数字的所有排列，然后判断有没有某一个的排列符合题目给定的条件，即a1＋a2＋a3＋a4＝a5＋a6＋a7＋a8，a1＋a3＋a5＋a7＝a2＋a4＋a6＋a8，并且a1＋a2＋a5＋a6＝a3＋a4＋a7＋a8。 2．在8×8的国际象棋上摆放8个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角线上。图4.16中的每个黑色格子表示一个皇后，这就是一种符合条件的摆放方法。请问总共有多少种符合条件的摆法？  图4.16 8×8的国际象棋棋盘上摆着8个皇后（黑色小方格），任意两个皇后不在同一行、同一列或者同一对角线上 由于8个皇后的任意两个不能处在同一行，那么肯定是每一个皇后占据一行。于是我们可以定义一个数组ColumnIndex\[8\]，数组中第i个数字表示位于第i行的皇后的列号。先把数组ColumnIndex的8个数字分别用0～7初始化，接下来就是对数组ColumnIndex做全排列。因为我们是用不同的数字初始化数组，所以任意两个皇后肯定不同列。我们只需判断每一个排列对应的8个皇后是不是在同一对角线上，也就是对于数组的两个下标i和j，是不是i-j=ColumnIndex\[i\]-ColumnIndex\[j\]或者j-i=ColumnIndex\[i\]-ColumnIndex\[j\]。 举一反三： 如果面试题是按照一定要求摆放若干个数字，我们可以先求出这些数字的所有排列，然后再一一判断每个排列是不是满足题目给定的要求。 4.5 本章小结 面试的时候我们难免会遇到难题，画图、举例子和分解这三种办法能够帮助我们解决复杂的问题（如图4.17所示）。  图4.17 解决复杂问题的三种方法：画图、举例子和分解。 图形能使抽象的问题形象化。当面试题涉及链表、二叉树等数据结构时，如果在纸上画几张草图，题目中隐藏的规律就有可能变得很直观。 一两个例子能使抽象的问题具体化。很多与算法相关的问题都很抽象，未必一眼就能看出它们的规律。这个时候我们不妨举几个例子，一步一步模拟运行的过程，说不定就能发现其中的规律，从而找到解决问题的窍门。 把复杂问题分解成若干个小问题，是解决很多复杂问题的有效方法。如果我们遇到的问题很大，可以尝试先把大问题分解成小问题，然后再递归地解决这些小问题。分治法、动态规划等方法都是应用分解复杂问题的思路。