# Java solution based on height, check left and right node in every recursion to avoid further useless search

• ``````public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
return height(root)!=-1;

}
public int height(TreeNode node){
if(node==null){
return 0;
}
int lH=height(node.left);
if(lH==-1){
return -1;
}
int rH=height(node.right);
if(rH==-1){
return -1;
}
if(lH-rH<-1 || lH-rH>1){
return -1;
}
return Math.max(lH,rH)+1;
}``````

• Great code, but the first

`````` if(root==null){
return true;
}
``````

is unnecessary because it will be checked within the height function.

• This post is deleted!

• Great! Much better than my answer which cost O(N2)...

• My code is more concise

``````    /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
return getDepth(root)!=-1;
}

public int getDepth(TreeNode root){
if(root==null){
return 0;
}
int left = getDepth(root.left);
if(left!=-1){
int right = getDepth(root.right);
if(right!=-1){
return Math.abs(left-right)<=1?1+Math.max(left,right):-1;
}
}
return -1;
}
}
``````

• This post is deleted!

• Good idea using -1 as unbalanced signal alternatively you could use a reference parameter or pointer or whatever you language offers. Here's a C# version

``````    public bool IsBalanced(TreeNode root)
{
bool result = true;
int depth = Depth(root, ref result);
return result;
}

public int Depth(TreeNode node, ref bool result)
{
if (result == false || node == null) return 0;
int leftDepth = Depth(node.left, ref result);
int rightDepth = Depth(node.right, ref result);

if (leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1)
{
result = false;
}

return 1 + Math.Max(leftDepth, rightDepth);
}
``````

• good solution using -1 as a boolean marker!

• Hey @mingyuan, your solution is really elegant. However, I am not able to understand why my solution's logic is incorrect. Do you have any idea? Here is the code:

``````public class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
return     Math.abs(h(root.left) - h(root.right))<=1 ;

}

public int h(TreeNode root){
if(root==null) return 0;
return (1 + Math.max(h(root.left),h(root.right)));
}
}
``````

• This post is deleted!

• return Math.abs(h(root.left) - h(root.right))<=1 && isBalanced(root.left) && isBalacend(root.right)

• ``````public class Solution {

boolean flag;
public boolean isBalanced(TreeNode root) {
flag = true;
judge(root);
return flag;
}

public int judge(TreeNode tNode){
if(tNode == null) return 0;
int leftLen = 1 + judge(tNode.left);
int rightLen = 1 + judge(tNode.right);
if(Math.abs(rightLen - leftLen) > 1){
flag = false;
return -1;
}
return leftLen > rightLen ? leftLen : rightLen;
}
}
``````

• @Eva001 why are you returning -1 after setting flag to false

• @jdrogin why have you taken result == false in first statement of depth

• Great idea! I can understand that this avoid unnecessary repeated work. But can someone please tell me that, does this idea apply any concept in DFS? It seems like DFS to me, for it runs recursively till it hits the leaf node. But it is a little weird that it doesn't use Stack... from my concept DFS is something that must associate with Stack, isn't it?

Please correct me if I'm wrong, thanks!

• @abhinav_smart
I guess here -1 is a boolean marker, since the types of return value of two functions are different.

• @mingyuan It seems be AVL tree algorithm. Here is my code which runs more time, because it caculates repeatedly.

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

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