使用旋转的二叉树变换

该答案来自《 CLRS第三版》教科书第13.2-4题。

让

LEFT =整个左链表二进制树

RIGHT =整个右链表二进制树。

您可以轻松（n-1）旋转将LEFT左右旋转。

例如：n = 3     3 2 1  2比1 3比21 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上限旋转中进行此 *** 作。

希望这会有所帮助！=）很快志隆， 多伦多大学