由递归式求n阶汉诺塔移动次数：
由递归式可知：
又因当n=1时，T(1)=1，得：
解得n阶汉诺塔移动次数为： 次。
汉诺塔与二进制
公式
这就像是n位二进制的和，最终得到n位二进制的最大值（全1）
所以有，n阶汉诺塔移动次数等于n位二进制得最大值，如：4阶汉诺塔移动次数为
每个盘子的移动次数，观察下图：
如图可知，每个盘子移动总次数刚好相反，
所以，n阶汉诺塔的第i个盘子总的移动次数为：
3阶汉诺塔图解与二进制关系
汉诺塔与满二叉树
递归算法会有相对应的递归树，而汉诺塔的递归树刚好是满二叉树，即所有分支结点都有两个叶子结点。
调整汉诺塔对算法代码的输出信息后：
public class Hanoi {
// 阶数
private static int n = 3;
public static void main(String[] args) {
System.out.println(String.format("%s层汉诺塔的移动顺序：", n));
int sum = moveTree(n, 'A','B','C');
System.out.println("汉诺塔移动次数："+sum);
}
/**
* 汉诺塔与满二叉树
* (n-1) A -> B
* n A -> C
* (n-1) B -> C
*
* 结束条件为：当n=1 时， A -> C
*/
public static int moveTree(int n,char A, char B, char C) {
if(n==1)
System.out.println(String.format("第 %s 层(叶子节点)：%s -> %s",n, A, C));
else {
moveTree(n-1, A, C, B);//每次都是输出A->C，所以要看到A->B，就需要将B和C交换
if(n==Hanoi.n)
System.out.println(String.format("第 %s 层(根节点)：%s -> %s", n, A, C));
else
System.out.println(String.format("第 %s 层(分支结点)：%s -> %s", n, A, C));
moveTree(n-1, B, A, C);//每次都是输出A->C，所以要看到B->C，就需要将A和B交换
}
//汉诺塔的移动次数为: 2^n-1
return (int) Math.pow(2, n)-1;
}
}
3阶汉诺塔对应的满二叉树：
3阶汉诺塔的移动步骤为满二叉树的中序遍历：AC、AB、CB、AC、BA、BC、AC
从输出结果可以看到，汉诺塔盘子编号对应满二叉树自底向上计算的层号，如：1号盘子的移动对应是叶子节点，最底层盘子对应根节点。
为了更好理解，可以写成这样：
public static int moveTree(int n,char A, char B, char C) {
if(n==1)
System.out.println(String.format("第 %s 层(叶子节点)：%s -> %s",Hanoi.n-n+1, A, C));
else {
moveTree(n-1, A, C, B);//每次都是输出A->C，所以要看到A->B，就需要将B和C交换
if(n==Hanoi.n)
System.out.println(String.format("第 %s 层(根节点)：%s -> %s", Hanoi.n-n+1, A, C));
else
System.out.println(String.format("第 %s 层(根节点)：%s -> %s", Hanoi.n-n+1, A, C));
moveTree(n-1, B, A, C);//每次都是输出A->C，所以要看到B->C，就需要将A和B交换
}
//汉诺塔的移动次数为: 2^n-1
return (int) Math.pow(2, n)-1;
}
汉诺塔递归实现与二叉树中序遍历的递归实现，在代码实现上很类似
public static void inorder(TreeNode root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.val);
inorder(root.right);
}
汉诺塔的移动步骤可以用满二叉树的中序遍历来表示，反过来，我们可以通过满二叉树的特性推导出汉诺塔的一些特性：
最后附上三者的关系图
总结
如果这些结论都是自己推导发现的话，你会发现充满惊喜。其推导过程非常有意思，好像冥冥之中万物都和二进制相关。文章想表达的不仅仅是得出汉诺塔有哪些特性，更重要的是希望能在学习中，发现学习本身的乐趣，从而滋养内在的好奇心、探索精神，不断地自我推进，让学习越来越有趣越有动力。