# 0ms Accepted Simple Recursive Java Solution

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

• I think yours may have to compute the height of some subtrees many times. You can use dp to solve this problem. : )

• Yeah true. thanks!

• dp means dynamic programming, you can record the trees you have searched so that you don't need to search it again. I use another class to remember whether each tree is balanced.

``````public class Solution {
class TreeNode2{
private TreeNode2 left;
private TreeNode2 right;
private int height;
private boolean isBalanced;

private TreeNode2(int value){
height = value;
}

private void setHeight(){
if(null == this.left && null == this.right) this.height = 1;
else if(null == this.right) this.height =  this.left.height + 1;
else if(null == this.left) this.height = this.right.height + 1;
else this.height = Math.max(this.left.height, this.right.height) + 1;
return;
}

public String toString(){
return this.height + "," + this.isBalanced;
}
}

public boolean isBalanced(TreeNode root){
TreeNode2 croot = copyTree(root);
return null == croot ? true : croot.isBalanced;
}

private TreeNode2 copyTree(TreeNode root){
if(null == root) return null;
//copy root
TreeNode2 croot = new TreeNode2(1);
//copy left subtree.
croot.left = copyTree(root.left);
//check whether left tree is balanced, if left tree is unbanlanced ,then return directly.
if(null != croot.left && ! croot.left.isBalanced){
croot.isBalanced = false;
return croot;
}
//copy right subtree
croot.right = copyTree(root.right);
if(null != croot.right && ! croot.right.isBalanced){
croot.isBalanced = false;
return croot;
}
int leftHeight = null == croot.left ? 0 : croot.left.height;
int rightHeight = null == croot.right ? 0 : croot.right.height;
if(Math.abs(leftHeight - rightHeight) > 1){
croot.isBalanced = false;
}
else{
croot.isBalanced = true;
}
croot.setHeight();
return croot;
}
``````

}

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