我选择了一个很好的面试问题。谁能帮我解释一下?
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 旋转就足够了(通过模拟),但我无法证明,哪位专家可以帮助我证明或想法?
最佳答案
树从 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 。
关于algorithm - 转换一棵树需要多少 Right Rotation?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29276657/