檢查二叉樹是否與迭代函數平衡？

Question

我需要實現一個非遞歸函數來確定二叉樹是否平衡。

有人嗎？

謝謝！

Answer 1

假設由「平衡」，你的意思是「高度平衡」的AVL樹感覺，你可以存儲任意信息爲每個節點，

• 對於後序的每個節點，
  • 如果其中一個孩子不存在，則假設其各自的身高爲0.
  • 如果兩個孩子的身高相差超過一個，那麼樹就不平衡。
  • 否則，此節點的高度是兩個孩子身高中較大的一個。
• 如果達到了這一點，樹就是平衡的。

一種方式進行後序遍歷：在根

• 開始
• 環
  • 如果此節點的左子存在，沒有它的高度計算，請訪問其左孩子旁邊。
  • 否則，如果此節點的右側子節點存在並且沒有計算其高度，請訪問其右側的子節點。
  • 其他
    • 計算此節點的高度，可能返回早
    • 如果此節點是不是根，下次光臨其父。
• 如果達到了這一點，樹就是平衡的。