Question

很多读者可能都知道各个击破的军事思想，这种思想的精髓是当敌我实力悬殊时，我们可以把强大的敌人分割开来，然后集中优势兵力打败被分割开来的小部分敌人。要一下子战胜总体很强大的敌人很困难，但战胜小股敌人就容易多了。同样，在面试中当我们遇到复杂的大问题的时候，如果能够先把大问题分解成若干个简单的小问题，然后再逐个解决这些小问题，那可能也会容易很多。

我们可以按照解决问题的步骤来分解复杂问题，每一步解决一个小问题。比如在面试题26复杂链表的复制中，我们将复杂链表复制的过程分解成三个步骤。在写代码的时候我们为每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。

在计算机领域有一类算法叫分治法，即分而治之，采用的就是各个击破的思想。我们把分解之后的小问题各个解决，然后把小问题的解决方案结合起来解决大问题。比如面试题27二叉搜索树与双向链表中，转换整个二叉树是一个大问题，我们先把这个大问题分解成转换左子树和右子树两个小问题，然后再把转换左右子树得到的链表和根结点链接起来，就解决了整个大问题。通常分治法思路都可以用递归的代码实现。

在面试题28字符串的排列中，我们把整个字符串分为两部分：第一个字符及它后面的所有字符。我们先拿第一个字符和后面的每个字符交换，交换之后再求后面所有字符的排列。整个字符串的排列是一个大问题，那么第一个字符之后的字符串的排列就是一个小问题。因此这实际上也是分治法的应用，可以用递归实现。