在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制: (1) 每次只能移动一个盘子; (2) 盘子只能从柱子顶端滑出移到下一根柱子; (3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]示例2:
输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]提示:
- A中盘子的数目不大于14个。
解题思路：递归
我们在刚接触递归算法的时候，常常会见到汉诺塔问题，而我们常常就会习惯性的想遇到汉诺塔问题就是用递归解决，但是为什么能用递归来解决问题呢，这个我们可能很少人去思考这个问题，所以我们就要来讨论一下为什么汉诺塔问题可以使用递归来解决，才能真正理解递归思想！
1、分析题目
我们可以试着列举 N 为不同大小时候的情况，看看有没有什么规律，如下图所示：
可以明显看到，当 N = 1 的时候，此时我们只需要做一个将柱子 A 上的盘子移动到柱子 C 即可！
然后当我们在进行 N = 2、N = 3、N = 4 以及 N = n 操作的时候，可以发现，它们的操作都可以分为三步来进行，首先将柱子 A 上的 n-1 个盘子借助柱子 C 放到柱子 B 上，然后将柱子 A 上最后一个盘子放到柱子 C 上，最后将柱子 B 上剩下的盘子放到柱子 C 上。
当在直接 N = 4 的操作的时候，将柱子 A 上面的 3 个盘子借助柱子 C 放到柱子 B 上去的操作是一个过渡过程，最重要的操作其实就是将柱子 A 上面的最后一个盘子放到柱子 C 上，然后剩下的盘子也放到柱子 C 上，其实这就好比 N = 4 的时候我们只需要关心将最后一个盘子放到柱子 C 上即可，而期间过渡操作也就是将剩下的盘子移动到柱子 C 上，其实可以看作是 N = 3 的操作！
以此类推，N = n 操作的时候，只需要关心将最后一个盘子放到柱子 C 上，然后剩下的两个盘子交给 N = n-1 去处理即可。直到最后处理到 N = 1 的时候，此时只需要做一个将柱子 A 上的盘子移动到柱子 C 即可！
2、为什么使用递归
通过上面的分析可以看出，我们在解决 N = n 的汉诺塔问题的时候，发现是可以交给子问题也就是 N = n-1 去处理的，因为那就是它要处理的工作，而我们只需要关心 N = n 中的一些细节；而对于 N = n-1 来说也是如此，它只需要处理一些小细节，然后剩下的工作交给子问题也就是 N = n-2 去处理，以此类推……
对于这样子出现一个大问题能够交给具有共同特征的小问题去解决，然后小问题又能交给其具有共同特征的小小问题去解决的话，就可以采用递归的思想，我们只需要关心其中的一步以及最后的递归结束条件即可！
3、如何编写递归的代码
之前我们讲过，分为三步走：
-
重复子问题，也就是设计函数头：
-
因为我们在挪动盘子的时候，需要指定盘子的数量，所以需要一个变量表示盘子的数量；然后还需要三个数组，分别代表的是三个柱子，分别为
x、y、z，表示将柱子x中的盘子，通过辅助柱子y放到柱子z中去，这样子我们在传参的时候就可以控制这些目的柱子是哪个了！void Move(vector<int>& x, vector<int>& y, vector<int>& z, int n); // 表示从柱子x中拿取n个盘子，通过柱子y放到柱子z中去
-
-
只关心某一个子问题的处理，也就是设计函数体：
-
因为我们只需要关心某个子问题，所以根据上面在分析题目的样例的时候，我们可以分为三步走，首先将柱子
A上的n-1个盘子借助柱子C放到柱子B上，然后将柱子A上最后一个盘子放到柱子C上，最后将柱子B上剩下的盘子放到柱子C上。 -
总结起来就是如下代码：
// 1. 先将柱子x中n-1个盘子通过柱子z，放到辅助柱子y上去 Move(x, z, y, n - 1); // 2. 然后将x的最后一个盘子放到z上去 z.push_back(x.back()); x.pop_back(); // 3. 最后将辅助柱子y上的n-1个盘子通过柱子x放到柱子z上去 Move(y, x, z, n - 1);
-
-
设置递归的出口，也就是设计递归结束条件：
-
因为特殊情况就是当
N = 1的时候，只需要将柱子x上的盘子移动到柱子z上面即可！// 函数终止条件 if(n == 1) { z.push_back(x.back()); x.pop_back(); return; }
-
4、代码实现
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
Move(A, B, C, A.size());
}
// 表示从柱子x中拿取n个盘子，通过柱子y放到柱子z中去
void Move(vector<int>& x, vector<int>& y, vector<int>& z, int n)
{
// 函数终止条件
if(n == 1)
{
z.push_back(x.back());
x.pop_back();
return;
}
// 1. 先将柱子x中n-1个盘子通过柱子z，放到辅助柱子y上去
Move(x, z, y, n - 1);
// 2. 然后将x的最后一个盘子放到z上去
move(x, y, z, 1);
// 3. 最后将辅助柱子y上的n-1个盘子通过柱子x放到柱子z上去
Move(y, x, z, n - 1);
}
};