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

Question

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

任何人？

谢谢!!!

Answer 1

假设通过"平衡",你的意思是AVL树意义上的"高度平衡",你可以存储每个节点的任意信息,

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

执行订单后遍历的一种方法:

• 从根开始
• 环
  • 如果此节点的左子节点存在且未计算其高度,请访问其左侧子节点.
  • 否则,如果此节点的右子节点存在且未计算其高度,请访问其右边的子节点.
  • 其他
    • 计算此节点的高度,可能提前返回
    • 如果此节点不是根节点,请访问其父节点.
• 如果达到此点,则树是平衡的.