GeeksForGeeks - POTD | GFG POTD Answer

class Solution
{
    public:
    void rec(Node* root, int i, int j,map<int,int> &mp)
    {
        if(root==NULL) return;
        mp[i-j] +=root->data;
        rec(root->left,i+1,j-1,mp);
        rec(root->right,i+1,j+1,mp);
    }
    vector <int> diagonalSum(Node* root) 
    {
        map<int,int> mp;
        vector<int> ans;
        rec(root,0,0,mp);
        for(auto val : mp) ans.push_back(val.second);
        return ans;
    }
};

public:
    //Function to store the zig zag order traversal of tree in a list.
    vector <int> zigZagTraversal(Node* root)
{
 vector<int> ans;
 queue<Node*> q;
 q.push(root);
 int k = 0;
 while(!q.empty()) {
  int n = q.size();
  vector<int> tmp;
  for(int i = 0; i < n; i++) {
   auto t = q.front(); q.pop();
   if(t->left) q.push(t->left);
   if(t->right) q.push(t->right);
   tmp.push_back(t->data);
  }
  if(k&1) ans.insert(ans.end(), tmp.rbegin(), tmp.rend());
  else ans.insert(ans.end(), tmp.begin(), tmp.end());
  k++;
 }
 return ans;
}
};

class Solution
{
public:
    int mxh=0,mxsum=0;
    void fun(Node* root, int h, int sum){
         if(root==NULL){
              if(mxh<h){
                   mxh=h;
                   mxsum=sum;
              }
              else if(h==mxh) mxsum=max(mxsum,sum);
              return;
         }
         fun(root->left,h+1,sum+root->data);
         fun(root->right,h+1,sum+root->data);
         return;
         
    }
    int sumOfLongRootToLeafPath(Node *root)
    {
       
        fun(root,0,0);
        return mxsum;
    }
};

class dsu {
    public:
    vector<int> parent;
    vector<int> size;
    //vector<int> rank;
    int n;
    dsu(int n) {
        this->n = n;
        parent.resize(n+1);
        size.resize(n+1);
       // rank.resize(n+1);
        for(int i=0;i<=n;i++) {
            parent[i] = i;
            size[i] = 1;
            //rank[i] = 0;
        }
    }
    int findparent(int x) {
        if(parent[x]==x) {
            return x;
        }
        return parent[x] = findparent(parent[x]);
    }
    int unionbysize(int x,int y,int &ans) {
        int px = findparent(x);
        int py = findparent(y);
        if(px==py) return size[px]*size[py];
        if(size[px]>size[py]) 
        {
            ans+=size[px]*size[py];
            parent[py] = px;
            size[px]+=size[py];
        }
        else 
        {
            ans+=size[px]*size[py];
            parent[px] = py;
            size[py]+=size[px];
        }
        return ans;
    }
   
};
class Solution{
 public:
 vector<int> maximumWeight(int n, vector<vector<int>> edges, int q, vector<int> &queries)
 {
     // code here
     int ans=0;
     dsu d(n);
     vector<pair<int, pair<int, int>>> wt;
     for(int i = 0; i < n-1; i++)
     {
            wt.push_back({edges[i][2] , {edges[i][0], edges[i][1]}}); 
        }
        sort(wt.begin() , wt.end());
        map<int, int> mp;

       for(int i = 0;i < n-1; i++)
       {

           int a = wt[i].first;

           int b = wt[i].second.first;

           int c = wt[i].second.second;

           mp[a] = d.unionbysize(b,c,ans);
        }
        vector<int>res;
        for(int i=0;i<q;i++)
        {
            auto it=mp.upper_bound(queries[i]);
            if(it==mp.begin())
            {
                res.push_back(0);
            }
            else
            {
                it--;
                res.push_back(it->second);
            }
        }
        return res;
        }
};

class Solution {
public:
    vector<int> levelOrder(Node* root) {
        vector<int> result;
        if (root == nullptr)
            return result;

        queue<Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node* current = q.front();
            q.pop();
            result.push_back(current->data);

            if (current->left != nullptr)
                q.push(current->left);
            if (current->right != nullptr)
                q.push(current->right);
        }

        return result;
    }
};

class Solution{
  public:
    int countPairs(struct Node* head1, struct Node* head2, int x) {
        vector<int>arr1;
        vector<int>arr2;
        while(head1) arr1.push_back(head1->data),head1=head1->next;
        while(head2) arr2.push_back(head2->data),head2=head2->next;
        sort(arr1.begin(),arr1.end(),greater<int>()),sort(arr2.begin(),arr2.end());
        int i=0,j=0,cnt=0;
        while(i<arr1.size() && j<arr2.size()){
            if(arr1[i]+arr2[j]>x)i++ ;
            else if(arr1[i]+arr2[j]==x) cnt++,j++;
            else j++;
        }
        return cnt;
    }
};

class Solution
{
    public:
    void deleteNode(Node *del_node)
    {
       *del_node=*del_node->next;
    }

};

class Solution
{
    public:
    void sort(Node **head)
    {
        Node* curr=*head,*prev=NULL,*last=curr;
        while(curr && curr->next){
            Node* nn=curr->next;
            curr->next=curr->next->next;
            nn->next=prev;
            prev=nn;
            last=curr;
            curr=curr->next;
        }
        if(!curr)last->next=prev;
        else curr->next=prev;
    }
};

class Solution {
  public:
    int largestSubsquare(int n, vector<vector<char>> a) {
        vector<vector<int>> ver(n , vector<int>(n, 0)) , hor(n , vector<int>(n, 0));
        int side = 0;
        
        for(int i = 0; i < n ; i++){
            for(int j = 0 ; j < n ; j++){
                if(a[i][j] == 'X'){
                    ver[i][j] = i == 0 ? 1 : ver[i-1][j] + 1;
                    hor[i][j] = j == 0 ? 1 : hor[i][j-1] + 1;
                }
            }
        }
        
        for(int i = n-1 ; i >= 0 ; i--){
            for(int j = n-1 ; j >= 0 ; j--){
                int val = min(ver[i][j] , hor[i][j]);
                while(val > side){
                    if(ver[i][j-val+1] >= val and hor[i-val+1][j] >= val){
                        side = val;
                    }
                    val--;
                }
            }
        }
        
        return side;
    }
};