如何找到不平衡的AVL树的类型？

Question

我已经写了AVL-tree代码，但是我怎样才能写一段代码来发现我的树是否不平衡，它发现不平衡的类型是left，Right，Left，right和right？

Answer 1

您可以执行一个普通的DFS traversal，然后在每个节点上找到max height of the left subtree和max height of the right subtree。

如果所有节点都为abs(height_left - height_right) <= 1，则树是平衡的。

要找到不平衡树的类型(我想您指的是修复树所需的旋转类型)，您可以使用左子指针和右子指针来推断所需的旋转类型。