Leetcode-Solutions/balancedBT.cpp at master · varkey98/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int height(TreeNode* root,map<TreeNode*,int>& m)
    {
        if(!root)
            return -1;
        else if(m.find(root)!=m.end())
            return m[root];
        else
        {
            m[root] =max(height(root->left,m),height(root->right,m))+1;
            return m[root];
        }

    }
    void fun(TreeNode* root,bool* ret,map<TreeNode*,int>& m)
    {
       if(root)
        {
            if(abs(height(root->left,m)-height(root->right,m))>1)
                *ret=false;
            else
            {
                fun(root->left,ret,m);
                fun(root->right,ret,m);
            }
        }
    }

    bool isBalanced(TreeNode* root) {
            map<TreeNode*,int> m;

        bool ret=true;
        fun(root,&ret,m);
        return ret;
    }