LeetCode-in-Java
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
Solution
import com_github_leetcode.TreeNode;
/*
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
// Empty Tree is balanced
if (root == null) {
return true;
}
// Get max height of subtree child
// Get max height of subtree child
// compare height difference (cannot be more than 1)
int leftHeight = 0;
int rightHeight = 0;
if (root.left != null) {
leftHeight = getMaxHeight(root.left);
}
if (root.right != null) {
rightHeight = getMaxHeight(root.right);
}
int heightDiff = Math.abs(leftHeight - rightHeight);
// if passes height check
// - Check if left subtree is balanced and if the right subtree is balanced
// - If one of both are imbalanced, then the tree is imbalanced
return heightDiff <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int getMaxHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = 0;
int rightHeight = 0;
// Left
if (root.left != null) {
leftHeight = getMaxHeight(root.left);
}
// Right
if (root.right != null) {
rightHeight = getMaxHeight(root.right);
}
if (leftHeight > rightHeight) {
return 1 + leftHeight;
} else {
return 1 + rightHeight;
}
}
}