我有以下二叉树,我试图转换成目标二叉树(第二个树在后)使用最少的树旋转数。理论上这棵树的最小旋转次数是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向左旋转