/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int height(TreeNode* node, int& diameter)//그대로 사용
    {
        if(!node)
            return 0;
        int l = height(node->left, diameter);
        int r = height(node->right, diameter);
        diameter = max(diameter,l+r);
        return 1+max(l,r);
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        height(root,diameter);
        return diameter;

    }
};

class Solution {
private:
    int backspace(string &s){
        int i, j;
        for(i=j=0; i<s.length(); ++i){
            if(s[i]=='#'){
                if(j>0) j--;
            }
            else{
                s[j++] = s[i];
            }
        }
        return j;
    }
public:
    bool backspaceCompare(string S, string T) {
        int sLen = backspace(S);
        int tLen = backspace(T);
        if (sLen != tLen) return false;
        for (int i = 0; i < sLen; i++) {
            if (S[i] != T[i]) return false;
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* p = head;
        ListNode* q = head;
        int n = 0;
        while(p)
        {
            n++;
            p = p->next;
        }
        n = n/2;
        for(int i =0; i<n; i ++)
        {
            q = q->next;
        }
        return q;

    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string , vector<string>> mp;
        for(string s : strs)
        {
            string t = s;
            sort(t.begin(),t.end());
            mp[t].push_back(s);
        }
        vector<vector<string>> anagrams;
        for(auto m : mp)
        {
            anagrams.push_back(m.second);
        }
        return anagrams;
    }
};

class Solution {
public:
    bool isHappy(int n) {

        while(true)
        {
            int sum = 0;
            while(n!=0)
            {
                int lastDigit = n % 10;
                sum += lastDigit*lastDigit;
                n = n/10;
            }

            if(1 <= sum && sum <= 9)
            {
                if(sum == 1 || sum == 7)
                {
                    return true;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                n = sum;
            }
        }

    }
};