题解 | #汉诺塔问题#

总结：
1.汉诺塔问题是经典的递归问题，移动n个盘从left借助mid移动到right,可以分解为先将n-1个盘从left借助right移动到mid,再把第n个盘从left直接移动到right，之后再将mid处的n-1个盘从mid借助left移动到right.其中移动n-1个盘的过程又可以划分为类似的小问题，递归就可以解决。结束条件是移动1个盘时，直接移动即可返回上一层。

import java.util.*;

public class Solution {
    public ArrayList<String> getSolution(int n) {
        // write code here
        String left = "left",mid="mid",right="right";
        ArrayList<String> list = new ArrayList<>();
        hanota(n,left,mid,right,list);
        return list;
    }
    public void hanota(int n,String left,String mid,String right,List<String> list){
        String str;
        if(n==1){
            str = "move from "+left+" to "+right;
            list.add(str);
            return;
        }
        hanota(n-1,left,right,mid,list);
        str = "move from "+left+" to "+right;
        list.add(str);
        hanota(n-1,mid,left,right,list);
    }
}