algorithm - 转换一棵树需要多少 Right Rotation？

Question

我选择了一个很好的面试问题。谁能帮我解释一下？

Suppose a binary tree with 6 nodes is given, such that each node has only left childs. With how many "right rotate" operations (without any left rotates), we can convert this tree to a tree in which each node has only right childs?

我的解决方案:

我认为 n-1 旋转就足够了(通过模拟)，但我无法证明，哪位专家可以帮助我证明或想法？

Answer 1

树从 root 节点和左边的 5 个子节点(即 n-1 子节点)开始。每次围绕 root 旋转会使右边的 child 数量增加 1。因此在 5 次旋转(意味着 n-1 旋转)之后所有的 child 都会在右边.

归纳法证明:提出n 次旋转后右边有n 个 child 。

第 1 步:旋转 1 圈后，右边有 1 个 child 。

第二步:假设经过n次旋转后右边有n个 child ，并证明经过n+1次旋转后，有右边是 n+1 个 child 。