## 110. Balanced Binary Tree

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 depth of the two subtrees of _every _node never differ by 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.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return isBalancedHelper(root) != -1;
}

private int isBalancedHelper(TreeNode root){
if (root == null) return 0;
int left = isBalancedHelper(root.left);
int right = isBalancedHelper(root.right);
if (left == -1 || right== -1|| Math.abs(left - right) > 1) return -1;

return Math.max(left, right) + 1;
}
}
``````
``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# class Solution {
#     public boolean isBalanced(TreeNode root) {
#         return isBalancedHelper(root) != -1;
#     }

#     private int isBalancedHelper(TreeNode root){
#         if (root == null) return 0;
#         int left = isBalancedHelper(root.left);
#         int right = isBalancedHelper(root.right);
#         if (left == -1 || right== -1|| Math.abs(left - right) > 1) return -1;

#         return Math.max(left, right) + 1;
#     }
# }
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def helper(root):
if not root: return 0

left, right = helper(root.left), helper(root.right)
if left == -1 or right == -1 or abs(left - right) > 1: return -1

return max(left, right) + 1

return helper(root) != -1
``````