text: # Given a binary tree, determine if it is height-balanced.
  # For this problem, a height-balanced binary tree is defined as:
  # a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
  
  # Example 1:
  # Given the following tree [3,9,20,null,null,15,7]:
  #     3
  #    / \
  #   9  20
  #     /  \
  #    15   7
  # Return true.
  
  # Example 2:
  # Given the following tree [1,2,2,3,3,null,null,4,4]:
  #        1
  #       / \
  #      2   2
  #     / \
  #    3   3
  #   / \
  #  4   4
  # Return false.
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
      def isBalanced(self, root):
          """
          :type root: TreeNode
          :rtype: bool
          """
          # M1. 自顶向下 递归枚举
          def getDepth(root):
              if not root:
                  return 0
              return 1 + max(getDepth(root.left), getDepth(root.right))
  
          if not root:
              return True
          if abs(getDepth(root.left) - getDepth(root.right)) > 1:
              return False
          return self.isBalanced(root.left) and self.isBalanced(root.right)
  
          # M2. 优化 自顶向下 递归检查标记
          def dfs(root):
              if not root:
                  return 0
              left, right = dfs(root.left), dfs(root.right)
              if left == -1 or right == -1 or abs(left - right) > 1:
                  return -1
              return 1 + max(left, right)
          
          return dfs(root) != -1