Description

Submission

• Level-Order Traversal
• InOrder Traversal

#include <bits/stdc++.h>

using namespace std;

/*
 * Complete the swapNodes function below.
 */

struct Node
{
    Node* left;
    Node* right;
    int data;
    int depth;

    Node(int data, int depth)
        :
        left(NULL),
        right(NULL),
        data(data),
        depth(depth)
    {}
};

Node* buildTree(vector<vector<int>>& indexes)
{
    Node* root = new Node(1, 1);
    queue<Node*> q;
    q.push(root);
    for(int i = 0; !q.empty(); q.pop(), ++i) {
        Node* node = q.front();
        
        if(indexes[i][0] != -1) {
            node->left = new Node(indexes[i][0], node->depth + 1);
            q.push(node->left);
        }
        if(indexes[i][1] != -1) {
            node->right = new Node(indexes[i][1], node->depth + 1); 
            q.push(node->right);
        }
    }
    return root;
}


void inOrderTraversal(Node* root, vector<int>& res)
{
    if(root == NULL) return;
    inOrderTraversal(root->left, res);
    res.push_back(root->data);
    inOrderTraversal(root->right, res);
}

vector<int> inOrderTraversal(Node* root)
{
    vector<int> res;
    inOrderTraversal(root, res);
    return res;
}

void swapKMultipleDepth(Node* root, int k)
{
    queue<Node*> q;
    for(q.push(root); !q.empty(); q.pop())
    {
        if(q.front()->left != NULL) q.push(q.front()->left);
        if(q.front()->right != NULL) q.push(q.front()->right);
        if(q.front()->depth % k == 0) {
            Node* tmp = q.front()->left;
            q.front()->left = q.front()->right;
            q.front()->right = tmp;
        }
    }
}

vector<vector<int>> swapNodes(vector<vector<int>> indexes, vector<int> queries) {
    /*
     * Write your code here.
     */
    vector<vector<int>> res;
    Node* root = buildTree(indexes);

    for(int i = 0; i < queries.size(); ++i) {
        swapKMultipleDepth(root, queries[i]);
        res.push_back(inOrderTraversal(root));
    }
    return res;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    vector<vector<int>> indexes(n);
    for (int indexes_row_itr = 0; indexes_row_itr < n; indexes_row_itr++) {
        indexes[indexes_row_itr].resize(2);

        for (int indexes_column_itr = 0; indexes_column_itr < 2; indexes_column_itr++) {
            cin >> indexes[indexes_row_itr][indexes_column_itr];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    int queries_count;
    cin >> queries_count;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    vector<int> queries(queries_count);

    for (int queries_itr = 0; queries_itr < queries_count; queries_itr++) {
        int queries_item;
        cin >> queries_item;
        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        queries[queries_itr] = queries_item;
    }

    vector<vector<int>> result = swapNodes(indexes, queries);

    for (int result_row_itr = 0; result_row_itr < result.size(); result_row_itr++) {
        for (int result_column_itr = 0; result_column_itr < result[result_row_itr].size(); result_column_itr++) {
            fout << result[result_row_itr][result_column_itr];

            if (result_column_itr != result[result_row_itr].size() - 1) {
                fout << " ";
            }
        }

        if (result_row_itr != result.size() - 1) {
            fout << "\n";
        }
    }

    fout << "\n";

    fout.close();

    return 0;
}