方法一

递归
汉诺塔问题的解决方案可以分为3步：
1、把n-1个盘子从left 借助 right，搬到mid柱子上；
2、把剩下最大的那一个盘子从left搬到right柱子上；
3、把n-1个盘子从mid 借助 left，搬到right柱子上。
示意图如下：
图片说明
至于如何把n-1个盘子搬到另一个柱子上，同样参照上面的3步，不过此时柱子扮演的left，mid，right角色已经改变；对于n-2，n-3等等以此类推。
具体代码如下：

class Solution {
public:
    vector<string> solution;

    void Hanoi(int n, string left, string mid, string right){
        if (n==0) return;
        Hanoi(n-1,left,right,mid);//把n-1个盘子从left借助right搬到mid上去。
        solution.push_back("move from " + left + " to " + right);//把第n个盘子从left搬到right上。
        Hanoi(n-1,mid,left,right);//把n-1个盘子从mid借助left搬到right上去。
    }

    vector<string> getSolution(int n) {
        Hanoi(n, "left", "mid", "right");
        return solution;
    }
};

时间复杂度：O(2^N)。假设把n个盘子搬动耗时T(n)，则有T(n)=2T(n-1)+1，从而[T(n)+1]/[T(n-1)+1]=2，对该等比数列求解即可。
空间复杂度：O(N)。递归栈的深度。

方法二

非递归算法
这种方法比较难想到。移动过程主要分为4个步骤：
1、将当前柱子顶部的盘子1移动到顺时针的下一个柱子。
2、将当前柱子和剩余的另一根柱子比较，将其中的一根柱子的盘子移动到另一根柱子上（很显然，这种移动方式是固定的）
3、指针指向顺时针的下一根柱子。
4、遇到某一根柱子的盘子满了时，停止循环；否则回到步骤1。
注意点在于当n为奇数时，顺时针的柱子顺序为left,right,mid；当n为偶数时，顺时针的柱子顺序为left,mid,right。
以n=3为例，示意图如下：
图片说明
具体代码如下：

class Solution {
public:
    vector<string> solution;
    typedef struct
    {
        string name;
        vector<int> stack;
    }stack;

    void initStack(stack &a, stack &b, stack &c, int n)
    {
        for (int i = n; i >= 1; -- i){
            a.stack.push_back(i);
        }
        a.name = "left";
        if (n % 2 == 1){
            b.name = "right";
            c.name = "mid";
        }
        else{
            b.name = "mid";
            c.name = "right";
        }
    }

    void move(stack &a, stack &b)        // 将a中的栈顶元素移入b中 
    {
        solution.push_back("move from " + a.name + " to "+b.name);
        b.stack.push_back(a.stack.back());
        a.stack.pop_back();
    }

    void moveOneToOne(stack &a, stack &b)    // 算法的第二步就是对于输入的两个栈，将其中一个栈的栈顶元素移到另一个栈中 
    {
        // 任意两个不全为空的柱子的单次盘子移动方法是固定的
        if (a.stack.empty()){    // a如果空的，自然只能把b的元素移到a中
            move(b, a);
        } 
        else if (b.stack.empty()){    // b如果空的，自然只能把a的元素移到b中
            move(a, b);
        }
        else if (a.stack.back() > b.stack.back()){ // a的栈顶元素如果大于b的，自然只能把b的元素移到a中
            move(b, a);
        }
        else{    // b的栈顶元素如果大于a的，自然只能把a的元素移到b中
            move(a, b);
        }
    }

    bool isEnd(stack &b, stack &c, int n)    // 若有一根柱子满了，则循环结束
    {
        if (b.stack.size() == n || c.stack.size() == n){
            return true;
        }
        else{
            return false;
        }
    }

    void hanoi(int n, stack &A, stack &B, stack &C)
    {
        for (int i = 0;!isEnd(B, C, n); ++ i){
            if (i % 3 == 0){
                move(A, B);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(A, C);
            }
            else if (i % 3 == 1)
            {
                move(B, C);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(B, A);
            }
            else{
                move(C, A);
                if (isEnd(B, C, n)){
                    break;
                }
                moveOneToOne(C, B);
            }
        }
    }


    vector<string> getSolution(int n) {
        stack A,B,C;
        initStack(A, B, C, n);
        hanoi(n, A, B, C);
        return solution;
    }
};

时间复杂度：O(2^N)，因为总的移动次数没有减少，与方法一相比时间复杂度不会降低。
空间复杂度：O(N)，开辟了3个数组用来存放盘子编号。

题解 | #汉诺塔问题#

方法一

方法二