在我学习有关二叉树的中期课程时，我发现一条声明，可以将任意n节点二叉树转换为最多2 * n-2旋转的任何其他n节点二叉树。有什么证据吗？我找到了一些带有渐近符号的证明，但还不是很清楚。我的意思是有人可以解释/显示为什么如此吗？如果它说出n节点的二叉树，它是否包括根？
该答案来自《 CLRS第三版》教科书第13.2-4题。
让
LEFT =整个左链表二进制树
RIGHT =整个右链表二进制树。
您可以轻松（n-1）旋转将LEFT左右旋转。
例如：n = 3 3 2 1 2比1 3比2 1 3
证明：根据定义，每次右旋转都会使最右路径的长度至少增加1。因此，从最右路径开始的长度为1（最坏的情况），最多需要执行（n-1）旋转才能达到使其正确。
因此，您可以轻松得出结论：具有（n-1）个旋转的任意形状的具有n个节点的二叉树都可以旋转为RIGHT。让T_1作为您开始的节点让T_2作为您开始的节点。
您可以在（n-1）圈内将T_1旋转到RIGHT。同样，您可以在（n-1）圈内将T_2旋转到RIGHT。
因此，要将T_1旋转为T_2，只需将T_1旋转为RIGHT，然后进行反向旋转即可将RIGHT旋转为T_2。
因此，您可以在（n-1）+（n-1）= 2n-2上限旋转中进行此操作。
希望这会有所帮助！=） 很快志隆， 多伦多大学
