JAVA O(n) solution based on Maximum Depth of Binary Tree

• ``````public class Solution {
private boolean result = true;

public boolean isBalanced(TreeNode root) {
maxDepth(root);
return result;
}

public int maxDepth(TreeNode root) {
if (root == null)
return 0;
int l = maxDepth(root.left);
int r = maxDepth(root.right);
if (Math.abs(l - r) > 1)
result = false;
return 1 + Math.max(l, r);
}
}``````

• It would be better if you call that height instead of maxDepth.

• A revision without using global value is following, but your solution is definitely better performed when running:

``````    public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
if (Math.abs(height(root.left)-height(root.right)) <= 1)
return (isBalanced(root.left) && isBalanced(root.right));
return false;
}
public int height(TreeNode root) {
if (root == null)
return 0;
int left = height(root.left);
int right= height(root.right);
return (Math.max(left,right)+1);

}
}``````

• your solution will do lots of useless searching.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.