如何找到不平衡AVL樹的類型？

Question

我寫AVL樹代碼，但我怎麼能寫一個代碼來發現我的樹是不平衡的，它發現不平衡類型左，左，左右，左右和左右？

Answer 1

你可以做一個正常的DFS traversal，並在每個節點找到max height of the left subtree和max height of the right subtree。

然後，如果對於所有節點abs(height_left - height_right) <= 1樹均衡。

要找到不平衡樹的類型（我認爲你的意思是需要修復樹的旋轉類型），可以使用左側和右側子指針來推斷出需要的旋轉類型。