两个二叉树之间的旋转距离



我有以下二叉树,我试图转换成目标二叉树(第二个树在后)使用最少的树旋转数。理论上这棵树的最小旋转次数是5,然而,我能算出的最小值是6,我也复制了旋转,我错过了什么?

树: 1 3 / / 2 5 / / 4 7 / / 6 11 / / 9 12 / 8 10

目标树: 1 11 / / 9 12 / / 3 10 / / 2 5 / / 4 7 / 6 8

到目前为止我尝试的旋转(所有这些都需要6次旋转):

Order1: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9 Order2: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

Order3: Rotate left with root 7 and pivot 11 Rotate left with root 5 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

Order4: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 3 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 9

Order5: Rotate left with root 7 and pivot 11 Rotate left with root 7 and pivot 9 Rotate left with root 5 and pivot 11 Rotate left with root 5 and pivot 9 Rotate left with root 3 and pivot 11 Rotate left with root 3 and pivot 9

右转,根11,枢轴9
以根7和枢轴9向左旋转
以根5和枢轴9向左旋转
以根3和枢轴9向左旋转
以根9和枢轴11向左旋转

最新更新