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

|

710 Discussions

|

  • steven_major
     + 0 comments

    This problem description needs a bit of work - I do appreciate the examples and their clarity as I was able to deduce the actual index recording rules from them. That said, the provided instructions for recording the index values of a tree were wrong.

    From the instructions:

     - it is the first node visited, the first time visited
 - it is a leaf, should only be visited once
 - all of its subtrees have been explored, should only be visited once while this is true
 - it is the root of the tree, the first time visited

    This is not correct (doesn't match their provided solutions). This implies we record the first node visited, which will always be the left or right child of the root node. This also implies that if a node has a left and right child, we record the value of the node only after exploring both the left and right sub-trees. The examples make it clear that this is not the case.

    The actual logic for printing values seems to be: "record an index whenever arriving at a node and its left subtree is fully explored (true if there is no left sub-tree)". Note that this handles leaf nodes since they have no left subtree.

    i.e. the traversal logic to get the indices in the order they want is: traverse tree in an in-order, depth first way. Record the index for a node when arriving at that node AND that node's left subtree has been fully explored - happens when: - arriving at a node and it has no left sub-tree - arriving at a node from its left sub-tree

    I spent most of my time on this problem figuring that part out, which was frustrating

  • g503420777
     + 0 comments

    No need to build a tree. Just swap the numbers in the list.

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

def swap(nodes, depth, curr, k, result):
    if curr == -1: 
        return
    if depth % k == k - 1:
        nodes[curr][0], nodes[curr][1] = nodes[curr][1], nodes[curr][0]
    swap(nodes, depth + 1, nodes[curr][0], k, result)
    result.append(curr)
    swap(nodes, depth + 1, nodes[curr][1], k, result)

  • phongthuypts
     + 0 comments

    Java:

    private static Node createTree(Node root, List<List<Integer>> indexes)
    {
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 0;
        while(!queue.isEmpty() && (i < indexes.size()))
        {
            List<Integer> index = indexes.get(i++);
            Node n = queue.remove();
            if(index.get(0) > 1)
            {
                n.left = new Node(index.get(0));
                queue.add(n.left);
            }
            if(index.get(1) > 1)
            {
                n.right = new Node(index.get(1));
                queue.add(n.right);
            } 
        } 
        return root;
    } 
    
    private static void inOrder(Node root, List<Integer> indexes)
    {
        if(root == null)
            return;
        inOrder(root.left, indexes);
        indexes.add(root.data); 
        inOrder(root.right, indexes);
    }
    
    private static void swap(Node root, int level, int query)
    {
        if((root == null) || root.left == root.right)
            return;
        if((level % query) == 0)
        {
            Node a = root.left;
            root.left = root.right;
            root.right = a;
        }
        swap(root.left, level+1, query);
        swap(root.right, level+1, query);
    }
    
     public static List<List<Integer>> swapNodes(List<List<Integer>> indexes, List<Integer> queries) {
    // Write your code here
        List<List<Integer>> result = new ArrayList<>();
        Node root = new Node(1);
        createTree(root, indexes);
        for(Integer q : queries)
        {
            List<Integer> list = new ArrayList<>();
            swap(root, 1, q);
            inOrder(root, list);
            result.add(list);
        }
         
        return result;
    }

  • wanyunze
     + 0 comments

    You actually dont need to create a class. Here's a way using just function:

    sys.setrecursionlimit(1 << 30)
def create_tree(indexes):
    tree_arr = [-1 for _ in range(1025)]
    tree_arr[1] = 1

    _next = []
    frontier = [1]
    indexes_pos = 0
    while frontier:
        for v in frontier:

            if indexes_pos >= len(indexes):
                return tree_arr

            if v != -1:
                left_c, right_c = indexes[indexes_pos][0], indexes[indexes_pos][1]
                tree_arr[v] = [left_c, right_c]
                _next.append(left_c)
                _next.append(right_c)
                indexes_pos += 1

        frontier = _next
        _next = []

    return tree_arr


def swapNodes(indexes, queries):
    tree = create_tree(indexes)
    height = 1025
    controller = [0 for _ in range(height)]
    traverse_res = []
    
    def traverse(lvl, idx):
        if idx >= len(tree) or idx == -1:
            return
            
        left = tree[idx][0]
        right = tree[idx][1]
        if controller[lvl] == 1:
            left = tree[idx][1]
            right = tree[idx][0]
            
        traverse(lvl+1, left)
        traverse_res.append(idx)
        traverse(lvl+1, right)
        
        return
    
    res = []
    for q in queries:
        tmp = q
        while q < height-1:
            controller[q-1] = not controller[q-1]
            q += tmp
        traverse(0, 1)
        res.append(traverse_res)
        traverse_res = []
				
        
    return res

  • esmaeel_wahdan
     + 1 comment

    Someone tell the auther he writes a shitty problem description.