题解 | #汉诺塔问题#

#include <vector>
class Solution {
public:
    void dfs(int n, string left, string mid, string right, vector<string> &ans){
        if(n <= 0) return;
        //首先将left中的n - 1 个移动到中间，然后再将最下面的圆盘放到最右边
        dfs(n - 1, left, right, mid, ans);
        string temp = "move from " + left + " to " + right;
        ans.push_back(temp);
        dfs(n - 1, mid, left, right, ans);  
    }
  
    vector<string> getSolution(int n) {
        //汉诺塔问题是典型的的递归问题，只不过是在递归问题中进行了一些的输出
        string right = "right";
        string left = "left";
        string mid  ="mid";
        
        vector<string> ans;
        dfs(n, left, mid, right, ans);
        return ans;
    }
};