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(lHrH<1  lHrH>1){
return 1;
}
return Math.max(lH,rH)+1;
}
Java solution based on height, check left and right node in every recursion to avoid further useless search


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(leftright)<=1?1+Math.max(left,right):1; } } return 1; } }

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); }

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))); } }

@yash.shrivastav25 said in Java solution based on height, check left and right node in every recursion to avoid further useless search:
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; } }



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)); } }