Рубрики

Поменяйте местами узлы в бинарном дереве каждого k-го уровня

При заданном двоичном дереве и целочисленном значении k задача состоит в том, чтобы поменять местами узлы одного и того же k-го уровня, где k> = 1.

Примеры:

Input :  k = 2  and Root of below tree                     
      1             Level 1 
    /   \ 
   2     3          Level 2
 /     /   \
4     7     8       Level 3

Output : Root of the following modified tree
      1
    /   \
   3     2
 /  \   /  
7    8  4
Explanation : We need to swap left and right sibling 
              every second level. There is only one 
              even level with nodes to be swapped are
              2 and 3.


Input : k = 1 and Root of following tree
            
       1          Level 1
     /   \ 
    2     3       Level 2
  /  \ 
 4    5           Level 3
Output : Root of the following modified tree
       1
     /   \
    3     2
         /  \
        5    4
Since k is 1, we need to swap sibling nodes of
all levels.

Простое решение этой проблемы состоит в том, что для каждого нужно найти узлы-братья для каждого кратного k и поменять их местами.

Эффективным решением является отслеживание номера уровня в рекурсивных вызовах. И для каждого посещаемого узла проверьте, является ли номер уровня его дочерних элементов кратным k. Если да, то поменяйте местами два дочерних узла. Иначе, повторить для левых и правых детей.

Ниже приведена реализация вышеуказанной идеи.

C ++

// c ++ программа подкачки узлов
#include<bits/stdc++.h>

using namespace std;

  
// Узел двоичного дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// функция для создания нового узла дерева

Node* newNode(int data)

{

    Node *temp = new Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

  
// поменять местами два узла

void Swap( Node **a , Node **b)

{

    Node * temp = *a;

    *a = *b;

    *b = temp;

}

  
// Служебная функция меняет местами левый и правый узлы дерева
// каждого k-го уровня

void swapEveryKLevelUtil( Node *root, int level, int k)

{

    // базовый вариант

    if (root== NULL ||

            (root->left==NULL && root->right==NULL) )

        return ;

  

    // если в векторе подкачки присутствует текущий уровень + 1

    // тогда мы меняем левый и правый узел

    if ( (level + 1) % k == 0)

        Swap(&root->left, &root->right);

  

    // Повтор для левого и правого поддеревьев

    swapEveryKLevelUtil(root->left, level+1, k);

    swapEveryKLevelUtil(root->right, level+1, k);

}

  
// Эта функция в основном вызывает рекурсивную функцию
// swapEveryKLevelUtil ()

void swapEveryKLevel(Node *root, int k)

{

    // вызываем функцию swapEveryKLevelUtil с

    // начальный уровень как 1.

    swapEveryKLevelUtil(root, 1, k);

}

  
// Служебный метод для обхода дерева заказов

void inorder(Node *root)

{

    if (root == NULL)

        return;

    inorder(root->left);

    cout << root->data << " ";

    inorder(root->right);

}

  
// Код драйвера

int main()

{

    / * 1

        / /

       2 3

     ///

    4 7 8 * /

    struct Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->right->right = newNode(8);

    root->right->left = newNode(7);

  

    int k = 2;

    cout << "Before swap node :"<<endl;

    inorder(root);

  

    swapEveryKLevel(root, k);

  

    cout << "\nAfter swap Node :" << endl;

    inorder(root);

    return 0;

}

Джава

// Перестановка узлов программы Java

class GFG

{

  
// Узел двоичного дерева

static class Node 

    int data; 

    Node left, right; 

}; 

  
// функция для создания нового узла дерева

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.left = temp.right = null

    return temp; 

  

  

  
// Служебная функция меняет местами левый и правый узлы дерева
// каждого k-го уровня

static void swapEveryKLevelUtil( Node root, int level, int k) 

    // базовый вариант

    if (root== null || 

            (root.left==null && root.right==null) ) 

        return

  

    // если в векторе подкачки присутствует текущий уровень + 1

    // тогда мы меняем левый и правый узел

    if ( (level + 1) % k == 0

        {

            Node temp=root.left;

            root.left=root.right;

            root.right=temp;

        }

  

    // Повтор для левого и правого поддеревьев

    swapEveryKLevelUtil(root.left, level+1, k); 

    swapEveryKLevelUtil(root.right, level+1, k); 

  
// Эта функция в основном вызывает рекурсивную функцию
// swapEveryKLevelUtil ()

static void swapEveryKLevel(Node root, int k) 

    // вызываем функцию swapEveryKLevelUtil с

    // начальный уровень как 1.

    swapEveryKLevelUtil(root, 1, k); 

  
// Служебный метод для обхода дерева заказов

static void inorder(Node root) 

    if (root == null

        return

    inorder(root.left); 

    System.out.print(root.data + " "); 

    inorder(root.right); 

  
// Код драйвера

public static void main(String args[])

    / * 1

        / /

    2 3

    ///

    4 7 8 * /

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(3); 

    root.left.left = newNode(4); 

    root.right.right = newNode(8); 

    root.right.left = newNode(7); 

  

    int k = 2

    System.out.println("Before swap node :"); 

    inorder(root); 

  

    swapEveryKLevel(root, k); 

  

    System.out.println("\nAfter swap Node :" ); 

    inorder(root); 

}

  
// Этот код предоставлен Арнабом Кунду

питон

# Python программа для замены узлов

  
# Узел двоичного дерева

class Node:

  

    # конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
# Служебная функция поменяет местами левый узел и правый узел дерева
# каждого k-го уровня

def swapEveryKLevelUtil(root, level, k):

      

    # Базовый вариант

    if (root is None or (root.left is None and

                        root.right is None ) ):

        return 

  

    # Если в векторе подкачки присутствует текущий уровень + 1

    # тогда мы меняем левый и правый узел

    if (level+1)%k == 0:

        root.left, root.right = root.right, root.left

      

    # Повтор для левого и правого поддерева

    swapEveryKLevelUtil(root.left, level+1, k)

    swapEveryKLevelUtil(root.right, level+1, k)

  

      
# Эта функция в основном вызывает рекурсивную функцию
# swapEveryKLevelUtil

def swapEveryKLevel(root, k):

      

    # Вызовите функцию swapEveryKLevelUtil с

    # начальный уровень как 1

    swapEveryKLevelUtil(root, 1, k)

  
# Способ найти обход дерева деревьев

def inorder(root):

      

    # Базовый вариант

    if root is None:

        return 

    inorder(root.left)

    print root.data, 

    inorder(root.right)

  
# Код драйвера
«»»

          1

        / /

       2 3

     ///

    4 7 8

«»»

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.right.right = Node(8)

root.right.left = Node(7)

  

k = 2 

print "Before swap node :" 
inorder(root)

  
swapEveryKLevel(root, k)

  

print "\nAfter swap Node : "

inorder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа подкачки узлов

using System;

  

class GFG 

  
// Узел двоичного дерева

public class Node 

    public int data; 

    public Node left, right; 

}; 

  
// функция для создания нового узла дерева

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.left = temp.right = null

    return temp; 

  

  

  
// Служебная функция меняет местами левый и правый узлы дерева
// каждого k-го уровня

static void swapEveryKLevelUtil( Node root, int level, int k) 

    // базовый вариант

    if (root == null || 

            (root.left == null && root.right==null) ) 

        return

  

    // если в векторе подкачки присутствует текущий уровень + 1

    // тогда мы меняем левый и правый узел

    if ( (level + 1) % k == 0) 

        

            Node temp=root.left; 

            root.left=root.right; 

            root.right=temp; 

        

  

    // Повтор для левого и правого поддеревьев

    swapEveryKLevelUtil(root.left, level+1, k); 

    swapEveryKLevelUtil(root.right, level+1, k); 

  
// Эта функция в основном вызывает рекурсивную функцию
// swapEveryKLevelUtil ()

static void swapEveryKLevel(Node root, int k) 

    // вызываем функцию swapEveryKLevelUtil с

    // начальный уровень как 1.

    swapEveryKLevelUtil(root, 1, k); 

  
// Служебный метод для обхода дерева заказов

static void inorder(Node root) 

    if (root == null

        return

    inorder(root.left); 

    Console.Write(root.data + " "); 

    inorder(root.right); 

  
// Код драйвера

public static void Main(String []args) 

    / * 1

        / /

    2 3

    ///

    4 7 8 * /

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(3); 

    root.left.left = newNode(4); 

    root.right.right = newNode(8); 

    root.right.left = newNode(7); 

  

    int k = 2; 

    Console.WriteLine("Before swap node :"); 

    inorder(root); 

  

    swapEveryKLevel(root, k); 

  

    Console.WriteLine("\nAfter swap Node :" ); 

    inorder(root); 


  
// Этот код предоставлен Rajput-Ji


Выход:


Before swap node :
4 2 1 7 3 8 
After swap Node :
7 3 8 1 4 2 

Эта статья предоставлена Nishant_singh (pintu) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Поменяйте местами узлы в бинарном дереве каждого k-го уровня

0.00 (0%) 0 votes