# 110. Balanced Binary Tree

• Time: $O(n\log n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: bool isBalanced(TreeNode* root) { if (root == nullptr) return true; return abs(maxDepth(root->left) - maxDepth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right); } private: int maxDepth(TreeNode* root) { if (root == nullptr) return 0; return 1 + max(maxDepth(root->left), maxDepth(root->right)); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public boolean isBalanced(TreeNode root) { if (root == null) return true; return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && // isBalanced(root.left) && // isBalanced(root.right); } private int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: if not root: return True def maxDepth(root: Optional[TreeNode]) -> int: if not root: return 0 return 1 + max(maxDepth(root.left), maxDepth(root.right)) return abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 and \ self.isBalanced(root.left) and self.isBalanced(root.right)