Leetcode 110 Balanced Binary Tree
Given a binary tree, determine if it is heightbalanced.
For this problem, a heightbalanced 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.
Input: root = [3,9,20,null,null,15,7]
Output: true
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Input: root = []
Output: true

This question can be solved by Depth First Search and it is similar with question 104. Maximum Depth of Binary Tree.

From qusetion 104, we learned that to find the maximum depth we need to use dfs and max. For this question, to find if the tree is balancedheight, we need to find left subtree height and right subtree height then get the difference between the left and right subtree. If the difference is greater than 1, then it is not balancedheight otherwise it is balancedheight tree. Note that if there is None node or 1 node, they are both balanced binary tree.
def isBalanced(self, root: Optional[TreeNode]) > bool:
def dfs(root):
if not root: return [True,0]
left,right = dfs(root.left),dfs(root.right)
balanced = (left[0] and right[0] and abs(left[1]  right[1]) <=1)
return[balanced,1+max(left[1],right[1])]
return dfs(root)[0]