题解 | 汉诺塔问题

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 
# @return string字符串一维数组
#
class Solution:
    
    def getSolution(self , n: int) -> List[str]:
        # write code here
        ret=[]
        def move(start,end):
            ret.append("move from "+start+" to "+end)

        """
         left :起始位置
         mid : 中间辅助
         right : 目标位置

        """    
        def hannota(left,mid,right,n):
            if n==1:
                move(left,right)
                return
            hannota(left,right,mid,n-1)  # 将n-1 个搬迁到辅助mid
            move(left,right) # 移动最低层的n 
            hannota(mid,left,right,n-1) # 起始位置mid 辅助 left  目标位置rifht
   
        hannota("left","mid","right",n)
        return ret