We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Swap Nodes [Algo]
  5. Discussions

Swap Nodes [Algo]

Sort by

recency

|

717 Discussions

|

  • chenji2012
     + 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()

  • pm5277
     + 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; }

  • kv3943
     + 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;

    }

  • kv3943
     + 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;

    }

  • managuzram
     + 0 comments

    Python 3 Version, it's mostly the same as g503420777's code but it's derived from trying to analyze as normal node traversal

    sys.setrecursionlimit(2000)
def swapNodes(indexes, queries):
    # Write your code here
    result = []
    for k in queries:
        res = []
        swap(indexes, 1, 1, k, res)
        #inOrder(indexes, 1, res)
        result.append(res)
    return result

def swap(nodes, depth, idx, k, res):
    if idx == -1:
        return
    if depth % k == 0:
        nodes[idx - 1][0], nodes[idx - 1][1] = nodes[idx - 1][1], nodes[idx - 1][0]
    swap(nodes, depth + 1, nodes[idx - 1][0], k, res)
    res.append(idx)
    swap(nodes, depth + 1, nodes[idx - 1][1], k, res)
        
def inOrder(nodes, idx, result):
    left = nodes[idx - 1][0]
    right = nodes[idx - 1][1]
    if left != -1:
        inOrder(nodes, left, result)
    result.append(idx)
    if right != -1:
        inOrder(nodes, right, result)