Sort by

recency

|

718 Discussions

|

  • + 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);
    }
    
  • + 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()
    
  • + 0 comments

    include

    include

    include

    include

    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; }

  • + 0 comments

    SOLUTION

    include

    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;
    

    }

  • + 0 comments

    SOLUTION

    include

    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;
    

    }