Sort by

recency

|

718 Discussions

|

3 weeks ago+ 0 comments

Java Solution, using level order traversal using 2 queues Start with putting 1 in the primary queue, 1. poll from primary queue, check if you need to swap the child i.e level % k == 0. 2. add the child indexes in secondary queuue. repeat step 1 and 2 until primary queue is empty. once empty means level is done, go to next level. poll all the indexes from secondary and add into primary. do the inOrderTraversal of the tree and add the list to a list

public static List> swapNodes(List> indexes, List queries) { // Write your code here Queue primary = new LinkedList<>(); Queue secondary = new LinkedList<>();

    List<List<Integer>> res = new ArrayList<>();
    for (int k : queries) {
        primary.add(1);
        int level = 1;
        while (!primary.isEmpty()) {
            while (!primary.isEmpty()) {
                int p = primary.poll();
                List<Integer> child = indexes.get(p - 1);
                if (level % k == 0) { // swap left and right child
                    child.add(child.get(0));
                    child.remove(0);
                }
                child.stream().filter(ch -> ch != -1).forEach(secondary::add); //add the non null child to secondary queue representing next level
            }
            while (!secondary.isEmpty())
                primary.add(secondary.poll());
            level++;
        }
        List<Integer> traversal = new ArrayList<>();
        inOrderTraversal(1, indexes, traversal);
        res.add(traversal);
    }

    return res;
}

private static void inOrderTraversal(int root, List<List<Integer>> indexes, List<Integer> res) {
    int left = indexes.get(root - 1).get(0);
    if (left != -1)
        inOrderTraversal(left, indexes, res);
    res.add(root);
    int right = indexes.get(root - 1).get(1);
    if (right != -1)
        inOrderTraversal(right, indexes, res);
}

3 months ago+ 0 comments

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import deque

#
# Complete the 'swapNodes' function below.
#
# The function is expected to return a 2D_INTEGER_ARRAY.
# The function accepts following parameters:
#  1. 2D_INTEGER_ARRAY indexes
#  2. INTEGER_ARRAY queries
#



# very compact when to depict a tree
# use a list (or dic) of the nodes to represent the tree
# the ith node on the tree has the data of i+1
# so as long as you can find a node that is not -1 then you can find it child and kkep on 

sys.setrecursionlimit(2000)
# get the inorder from the i in tree
def inOrder(i, tree):
    # nothing to further check
    if i == -1:
        return []
    # get two sons for this non null node
    # note, its sons are in the i-1 position
    left, right = tree[i-1]

    return inOrder(left, tree) + [i] + inOrder(right, tree)


# make a list of list to track the depth (use the deque)
# 0: [1], 1:[2,3], can cause a blank list 
def getNodeDeepth(tree):
    depth_list = [[1]]
    # the initial queue
    depth_queue = deque([1])
    
    # those are in the same depth
    while depth_queue:
        # we are dealing a new depth of node
        depth_list.append([])
        for _ in range(len(depth_queue)):
            i = depth_queue.popleft()
            l,r = tree[i-1]
            if l != -1:
                depth_queue.append(l)
                depth_list[-1].append(l)
            if r != -1:
                depth_queue.append(r)
                depth_list[-1].append(r)
        if not depth_list[-1]:
            depth_list.pop()
    return depth_list     
            
        



def swapNodes(indexes, queries):
    #print(inOrder(1,indexes))
    depth_list = getNodeDeepth(indexes)
    
    ret = []
    for k in queries:
        i = 1
        while i * k <= len(depth_list):
            parents = depth_list[i * k -1]
            for p in parents:
                l,r = indexes[p -1]
                indexes[p -1] = r,l
            i += 1
        ret.append(inOrder(1,indexes))
    
    return ret
    # Write your code here

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input().strip())

    indexes = []

    for _ in range(n):
        indexes.append(list(map(int, input().rstrip().split())))

    queries_count = int(input().strip())

    queries = []

    for _ in range(queries_count):
        queries_item = int(input().strip())
        queries.append(queries_item)

    result = swapNodes(indexes, queries)

    fptr.write('\n'.join([' '.join(map(str, x)) for x in result]))
    fptr.write('\n')

    fptr.close()

4 months ago+ 0 comments

include

using namespace std; vector leftNode, rightNode; int swapLevel;

void traverse(int node=1){ if (node == -1) return; traverse(leftNode[node]); cout << node << " "; traverse(rightNode[node]); if (node == 1) cout << endl; }

void swap(int level=1, int node=1) { if (node == -1) return; if (level % swapLevel == 0) { int tmp = leftNode[node]; leftNode[node] = rightNode[node]; rightNode[node] = tmp; } swap(level+1, leftNode[node]); swap(level+1, rightNode[node]); }

int main() { int count;
cin>>count; leftNode.push_back(0); rightNode.push_back(0); while(count--){ int L, R; cin>>L>>R; leftNode.push_back(L); rightNode.push_back(R); } cin>>count; while(count--){ cin >> swapLevel; swap(); traverse(); } return 0; }

4 months ago+ 0 comments

SOLUTION

include

struct node { int id; int depth; struct node *left, *right; };

void inorder(struct node* tree) { if(tree == NULL) return;

inorder(tree->left);
printf("%d ",tree->id);
inorder((tree->right));

}

int main(void) { int no_of_nodes, i = 0; int l,r, max_depth,k; struct node* temp = NULL; scanf("%d",&no_of_nodes); struct node* tree = (struct node *) calloc(no_of_nodes , sizeof(struct node)); tree[0].depth = 1; while(i < no_of_nodes ) { tree[i].id = i+1; scanf("%d %d",&l,&r); if(l == -1) tree[i].left = NULL; else { tree[i].left = &tree[l-1]; tree[i].left->depth = tree[i].depth + 1; max_depth = tree[i].left->depth; }

     if(r ==  -1)
        tree[i].right = NULL;
    else
         {
             tree[i].right = &tree[r-1];
             tree[i].right->depth = tree[i].depth + 1;
             max_depth = tree[i].right->depth+2;
         }

i++;
}

scanf("%d", &i);
while(i--)
{
    scanf("%d",&l);
    r = l;
    while(l <= max_depth)
    {
        for(k = 0;k < no_of_nodes; ++k)
        {
            if(tree[k].depth == l)
            {
                temp = tree[k].left;
                tree[k].left = tree[k].right;
                tree[k].right = temp;
            }
        }
        l = l + r;
    }
    inorder(tree);
    printf("\n");
}



return 0;

}

4 months ago+ 0 comments

SOLUTION

include

struct node { int id; int depth; struct node *left, *right; };

void inorder(struct node* tree) { if(tree == NULL) return;

inorder(tree->left);
printf("%d ",tree->id);
inorder((tree->right));

}

     if(r ==  -1)
        tree[i].right = NULL;
    else
         {
             tree[i].right = &tree[r-1];
             tree[i].right->depth = tree[i].depth + 1;
             max_depth = tree[i].right->depth+2;
         }

i++;
}

scanf("%d", &i);
while(i--)
{
    scanf("%d",&l);
    r = l;
    while(l <= max_depth)
    {
        for(k = 0;k < no_of_nodes; ++k)
        {
            if(tree[k].depth == l)
            {
                temp = tree[k].left;
                tree[k].left = tree[k].right;
                tree[k].right = temp;
            }
        }
        l = l + r;
    }
    inorder(tree);
    printf("\n");
}



return 0;

}

Sort by

|

718 Discussions

|

include

include

include

include

include

include

include

include

include

Cookie support is required to access HackerRank