题解 | #判断是不是平衡二叉树#

递归法：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if self.get_height(root) != -1:
            return True
        else:
            return False
    
    def get_height(self, root: TreeNode) -> int:
        # Base Case
        if not root:
            return 0
        # 左
        if (left_height := self.get_height(root.left)) == -1:
            return -1
        # 右
        if (right_height := self.get_height(root.right)) == -1:
            return -1
        # 中
        if abs(left_height - right_height) > 1:
            return -1
        else:
            return 1 + max(left_height, right_height)

迭代法：

class Solution:
     def isBalanced(self, root: TreeNode) -> bool:
          st = []
          if not root:
              return True
          st.append(root)
          while st:
              node = st.pop() #中
              if abs(self.getDepth(node.left) - self.getDepth(node.right)) > 1:
                  return False
              if node.right:
                  st.append(node.right) #右（空节点不入栈）
              if node.left:
                  st.append(node.left) #左（空节点不入栈）
          return True

      def getDepth(self, cur):
          st = []
          if cur:
              st.append(cur)
          depth = 0
          result = 0
          while st:
              node = st.pop()
              if node:
                  st.append(node) #中
                  st.append(None)
                  depth += 1
                  if node.right: st.append(node.right) #右
                  if node.left: st.append(node.left) #左
              else:
                  node = st.pop()
                  depth -= 1
              result = max(result, depth)
          return result