右斜线性树转平衡AVL树的旋转操作及遍历实现方法

问题1：转换所需的总旋转次数 #

总共需要执行4次旋转操作。

问题2：单次遍历完成转换的方法 #

采用DSW（Day-Stout-Warren）算法即可实现单次遍历完成转换，逻辑如下：

• 原右斜树本身已经符合DSW算法要求的“右向主链（backbone）”结构，不需要额外做树的扁平化处理
• 只需要沿主链从根节点开始做一次线性遍历，按照预设的旋转规则对指定节点执行左旋操作即可，全程不需要额外存储节点数组，空间复杂度为O(1)，时间复杂度为O(n)

问题3：具体旋转操作步骤 #

原树为全右斜的二叉搜索树，中序遍历序列为[1,2,3,4,5,6]，所有旋转均为左旋操作，步骤如下：

每次左旋以当前主链上的指定节点为旋转轴

1. 第一次左旋：以节点1为轴旋转，旋转后根节点变为2，2的左孩子为1，右孩子为3，剩余主链保持3->4->5->6的右斜结构
2. 第二次左旋：以节点3为轴旋转，旋转后2的右孩子变为4，4的左孩子为3，右孩子为5，剩余主链保持5->6的右斜结构
3. 第三次左旋：以节点5为轴旋转，旋转后4的右孩子变为6，6的左孩子为5，此时主链变为2->4->6的右斜结构
4. 第四次左旋：以节点2为轴旋转，旋转后根节点变为4，4的左孩子为2，2的左孩子为1、右孩子为3，4的右孩子为6，6的左孩子为5
   旋转完成后所有节点的平衡因子绝对值均不超过1，符合平衡AVL树的要求。

内容的提问来源于stack exchange，提问作者Vembu karthick