# The Problem:

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.

# Notes:

- This problem can be tackled by examine left and right subtree balance of each node recursively. If either subtree is not balanced, or length difference of two subtrees is greater than 1, then return false.
- Recursion function should return the height of subtree, and we can use a flag of -1 to indicate an unbalanced subtree.

# Java Solution

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public boolean isBalanced(TreeNode root) { int res = getBalance(root); return (res!=-1); } private int getBalance ( TreeNode root){ if(root == null) return 0; int left = getBalance(root.left); int right = getBalance(root.right); if(left == -1 || right ==-1 || Math.abs(left-right) > 1) return -1; return Math.max(left, right) +1; } }

Advertisements