나는 트리 이식의 최소 횟수를 사용하여 대상 이진 트리 (게시물의 두 번째 트리)로 변환하려고하는 다음과 같은 이진 트리를 가지고 있습니다. 이 나무의 이론 최소 회전 수는 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