Simple Soln using hashmap (C++)


#1

/**

  • Definition for binary tree
  • struct TreeNode {
  • int val;
    
  • TreeNode *left;
    
  • TreeNode *right;
    
  • TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    
  • };
    /
    unordered_map<TreeNode
    ,int> table;
    int height(TreeNode* root)
    {
    if(!root) return 0;
    int left = height(root->left);
    int right = height(root->right);
    table[root] = max(left,right) +1;
    return max(left,right) +1;
    }
    int Solution::isBalanced(TreeNode* root) {
    if(!root) return 1;
    int l,r;
    if(table.find(root)==table.end())
    l = height(root->left);
    else
    l = table[root->left];
    if(table.find(root)==table.end())
    r = height(root->right);
    else
    r = table[root->right];
    int a = isBalanced(root->left);
    int b = isBalanced(root->right);
    if(a && b && abs(l-r)<=1)
    return 1;
    return 0;
    }