C++, using DP, Best solution?


#1
unordered_map<TreeNode*,int> mp;

int tree_length(TreeNode* A)
{
    if(A==NULL) return 0;
    if(mp.find(A)==mp.end()){
        mp[A]= max(tree_length(A->left),tree_length(A->right) );
    }
    
    return 1+mp[A];
    
}
bool balance(TreeNode* A)
{
    if(A==NULL) return true;
    if(abs(tree_length(A->left)- tree_length(A->right))>1 ) return false;
    
    if(balance(A->left)== false || balance(A->right)==false ) return false;
    
    return true;
}
 
int Solution::isBalanced(TreeNode* A) {
    mp.clear();
    if(balance(A)) return 1;
    
    return 0;
    
}