GeeksForGeeks - POTD | GFG POTD Answer

vector<int> noSibling(Node* root)
{
    vector<int> ans;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* node = q.front(); q.pop();
        int cnt = 0, tt = -1;
        if (node->left) {
            ++cnt; tt = node->left->data;
            q.push(node->left);
        }
        if (node->right) {
            ++cnt; tt = node->right->data;
            q.push(node->right);
        }
        if (cnt == 1) {
            ans.push_back(tt);
        }
    }

    if (ans.size() == 0) return {-1};

    sort(ans.begin(), ans.end());

    return ans;
}

class Solution{
  public:
    vector <int> verticalSum(Node *root) {
        vector<int> res;
        map<int,int> mp;
        queue<pair<Node*,int>> q;
        q.push({root,0});
        while(!q.empty()){
            Node * node = q.front().first;
            int line = q.front().second;
            q.pop();
            
            mp[line] += node->data;
            
            if(node->left)
                q.push({node->left,line-1});
            if(node->right)
                q.push({node->right,line+1});
        }
        for(auto i : mp){
            res.push_back(i.second);
        }
        return res;
    }
};

class Solution {
public:
    // Recursive function to construct a binary tree from inorder and postorder traversals
    Node* buildTree(int in[], int post[], int n) {
        // Base case: If no nodes, return nullptr
        if (n == 0) {
            return nullptr;
        }

        // Find the root node index in inorder traversal
        int rootIndex = 0;
        while (rootIndex < n && in[rootIndex] != post[n - 1]) {
            rootIndex++;
        }

        // Create the root node with the value from postorder traversal
        Node* root = new Node(post[n - 1]);

        // Recursively build left subtree using elements before root in inorder traversal
        Node* leftSubtree = buildTree(in, post, rootIndex);

        // Recursively build right subtree using elements after root in inorder traversal
        Node* rightSubtree = buildTree(in + rootIndex + 1, post + rootIndex, n - rootIndex - 1);

        // Connect left and right subtrees to the root node
        root->left = leftSubtree;
        root->right = rightSubtree;

        return root;
    }
};

class Solution
{
    public:
    vector<int> nodes;
    void traverse(struct Node* root, int k) {
        if(!root) return;
        if(k == 0) nodes.push_back(root -> data);
        traverse(root -> left, k - 1);
        traverse(root -> right, k - 1);
    }
    vector<int> Kdistance(struct Node *root, int k) {
        nodes.clear();
        traverse(root, k);
        return nodes;
    }
};

class Solution
{
    void inorder(Node *root, vector<int> &store){
        if(root == NULL)
            return;
            
        inorder(root->left, store);
        store.push_back(root->data);
        inorder(root->right, store);
    }
    
    public:
    //Function to serialize a tree and return a list containing nodes of tree.
    vector<int> serialize(Node *root) 
    {
        vector<int> str;
        inorder(root, str);
        return str;
    }
    
    //Function to deserialize a list and construct the tree.
    Node * deSerialize(vector<int> &A)
    {
        int n = A.size();
        Node *root = new Node(A[0]);
        
        for(int i=1; i<n; i+=2){
            Node *newRoot = new Node(A[i]);
            newRoot->left = root;
            if(i+1 < n){
                newRoot->right = new Node(A[i+1]);
            }
            root = newRoot;
        }
        return root;
    }

};

class Solution
{
    public:

    struct Node* arrangeCV(Node *head)
    {
       if(head==NULL || head->next==NULL)
       return head;
       
       Node *temp=head;
       
       Node *vDummy=new Node(-1);
       Node *cDummy=new Node(-1);
       
       Node *vcur=vDummy;
       Node *ccur=cDummy;
       
       while(temp!=NULL){
           if(temp->data=='a' || temp->data=='e' || temp->data=='i' || temp->data=='o' || temp->data=='u')
           {
               vcur->next=temp;
               vcur=vcur->next;
           }
           else{
               ccur->next=temp;
               ccur=ccur->next;
           }
           
           temp=temp->next;
       }
       
       vcur->next=cDummy->next;
       ccur->next=NULL;
       
       return vDummy->next;
    }
};

class Solution
{
    public:
    
    Node* rev(Node *head){
        Node *cur=head;
        Node *prev=NULL;
        Node *after=NULL;
        
        while(cur!=NULL){
            after=cur->next;
            cur->next=prev;
            prev=cur;
            cur=after;
        }
        
        return prev;
    }
    Node* addTwoLists(struct Node* num1, struct Node* num2)
    {
        // code here
        if(num1==NULL)
        return num2;
        
        if(num2==NULL)
        return num1;
        
        Node *temp=new Node(-1);
        Node *cur=temp;
        
        Node *l1=rev(num1);
        Node *l2=rev(num2);
        
        int carry=0;
        
        while((l1!=NULL || l2!=NULL) || carry){
            int sum=0;
            if(l1!=NULL){
                sum+=l1->data;
                l1=l1->next;
            }
            if(l2!=NULL){
                sum+=l2->data;
                l2=l2->next;
            }
            
            sum+=carry;
            carry=sum/10;
            
            Node *node=new Node(sum%10);
            cur->next=node;
            cur=cur->next;
        }
        
        temp=rev(temp->next);
        while(temp->data==0 && temp->next!=NULL)
        temp=temp->next;
        
        return temp;
        
    }
};

class Solution {
    public:
    Node* deleteK(Node *head,int K){
    if(K == 1) return nullptr;
    Node* s = head;
    int cnt = 0;
    for(Node* s = head; s != nullptr; s = s->next) {
        cnt++;
        if(cnt == K-1){
            cnt = 0;
            if(s->next)
                s->next = s->next->next;
        }

    }
    return head;
}
};

class Solution{
    public:
    Node* deleteMid(Node* head)
    {
        if(head->next == NULL){
            return NULL;
        }
        Node* slow = head;
        Node* fast = head -> next;
        while(fast != NULL && fast->next != NULL && fast->next ->next != NULL){
            fast = fast -> next -> next;
            slow = slow -> next;
        }
        slow -> next = slow -> next -> next;
        return head;
    }
};

class Solution {
  public:

    struct Node *sortDoubly(struct Node *head) {
        if(head == NULL)
           return head;
        Node *temp = head;
        vector<int> arr;
        while(temp != nullptr){
            arr.push_back(temp->data);
            temp = temp->next;        
        }
        sort(arr.begin(), arr.end());
        struct Node *newNode = new Node(arr[0]);
        struct Node *dummyHead = newNode;
        for(int i = 1; i < arr.size(); i++){
            Node *temp_node = new Node(arr[i]);
            dummyHead->next = temp_node;
            temp_node->prev = dummyHead;
            dummyHead = temp_node;
        }
        return newNode;
    }
};