110. Balanced Binary Tree ⭐
Easy
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:
Input: root = [3,9,20,null,null,15,7]
Output:
true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4]
Output:
false
Example 3:
Input: root = []
Output:
true
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]. -104 <= Node.val <= 104
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isBalanced(root *TreeNode) bool {
if root == nil { return true }
left := helper(root.Left)
right := helper(root.Right)
return abs(left-right) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}
func helper(root *TreeNode) int {
if root == nil { return 0 }
return max(helper(root.Left), helper(root.Right)) + 1
}
func max(a, b int) int {
if a > b { return a }
return b
}
func abs(n int) int {
if n < 0 { return -n }
return n
}