方法一

递归
汉诺塔问题的解决方案可以分为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个数组用来存放盘子编号。