检查二叉树是否与迭代函数平衡？

Question

我需要实现一个非递归函数来确定二叉树是否平衡。

有人吗？

谢谢！

Answer 1

假设由“平衡”，你的意思是“高度平衡”的AVL树感觉，你可以存储任意信息为每个节点，

• 对于后序的每个节点，
  • 如果其中一个孩子不存在，则假设其各自的身高为0.
  • 如果两个孩子的身高相差超过一个，那么树就不平衡。
  • 否则，此节点的高度是两个孩子身高中较大的一个。
• 如果达到了这一点，树就是平衡的。

一种方式进行后序遍历：在根

• 开始
• 环
  • 如果此节点的左子存在，没有它的高度计算，请访问其左孩子旁边。
  • 否则，如果此节点的右侧子节点存在并且没有计算其高度，请访问其右侧的子节点。
  • 其他
    • 计算此节点的高度，可能返回早
    • 如果此节点是不是根，下次光临其父。
• 如果达到了这一点，树就是平衡的。