# Can we have a better solution

• Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

• I agree with shengwei.li.58, the code above didn't use shortcut in most efficient way in fact.

• This post is deleted!

• here is my solution:

``````class Solution {
public:
bool isBalanced(TreeNode *root) {
return do(root).first;
}
pair<bool,int> do(TreeNode *root){
if(!root) return make_pair(true,0);
pair<bool,int> a = do(root->left);
pair<bool,int> b = do(root->right);
if(!a.first||!b.first) return make_pair(false,0);
if(abs(a.second-b.second)>1)
return make_pair(false,0);
return make_pair(true,(a.second>b.second?a.second:b.second)+1);
}
};``````

• ``````bool isBalanced(node root) {
if(!root) return true;
bool left = isBalanced(root->left), right = isBalanced(root->right);
int left_dep = root->left ? root->left->val : 0,
right_dep = root->right ? root->right->val : 0;
root->val = max(left_dep, right_dep) + 1;
return left && right && abs(left_dep-right_dep)<2;
}
``````

since the node value is not used in this question, i use it to store the depth.

• ## Dynamic Programming & Short-Circuit

No need to calculate the height of same nodes repeatedly.

``````private static HashMap<TreeNode, Integer> treeHeightMap = new HashMap<>(); //for "memorizing" computed heights

public boolean isBalanced(TreeNode root) {
if(null == root) return true;
// my left son is balanced && my right son is balanced && I'm balanced
return isBalanced(root.left) && isBalanced(root.right) && ((Math.abs(computeHeight(root.left) - computeHeight(root.right))) < 2);
}

private static int computeHeight(TreeNode root){
if(null == root) return -1;
Integer height;
if (null == (height = treeHeightMap.get(root))){
height = Math.max(computeHeight(root.left), computeHeight(root.right)) + 1;
treeHeightMap.put(root, height);
}
return height;
}``````

• //The time complexity is O(N),but yous are O(N logN).

``````  public boolean isBalanced2(TreeNode root) {
if(checkHeight(root) == -1)
return false;
else
return true;
}
private int checkHeight(TreeNode root){
if(root == null)
return 0;

int leftHeight = checkHeight(root.left);
if(leftHeight == -1)
return -1;

int rightHeight = checkHeight(root.right);
if(rightHeight == -1)
return -1;

int heightDiff = leftHeight - rightHeight;
if(Math.abs(heightDiff) > 1)
return -1;
else
return Math.max(leftHeight,rightHeight)+1;
}
``````

• The time complexith is O(N),but yous are O(N longN).

``````public boolean isBalanced2(TreeNode root) {
if(checkHeight(root) == -1)
return false;
else
return true;
}

private int checkHeight(TreeNode root){
if(root == null)
return 0;

int leftHeight = checkHeight(root.left);
if(leftHeight == -1)
return -1;//not balance

int rightHeight = checkHeight(root.right);
if(rightHeight == -1)
return -1;//not balance

int heightDiff = leftHeight - rightHeight;
if(Math.abs(heightDiff) > 1)
return -1;//not balance
else
return Math.max(leftHeight,rightHeight)+1;//balance,return the true height
}``````

• This post is deleted!

• ``````class Solution:
# @param root, a tree node
# @return a boolean
def isBalanced(self, root):
h, b = self.getHB(root)
return b

def getHB(self, root):
if not root:
return 0, True
h1, b1 = self.getHB(root.left)
h2, b2 = self.getHB(root.right)
h = max(h1, h2) + 1
b = b1 and b2 and abs(h1-h2) <= 1
return h, b
``````

one recursion

• I tried to nest getHeight() within isBalanced(), but got an error? Can you do that?

• Will it lead to stack overflow? I have the same kind of code and it blows.

• `if(root == null || isBalanced == false)`

This will end unnecessary traversal.

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