Dado un árbol binario y un valor entero k, la tarea es intercambiar Nodes hermanos de cada k’ésimo nivel donde k >= 1.
Ejemplos:
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.
Una solución simple de este problema es que para cada es encontrar Nodes hermanos para cada múltiplo de k e intercambiarlos.
Una solución eficiente es realizar un seguimiento del número de nivel en las llamadas recursivas. Y para cada Node visitado, verifique si el número de nivel de sus hijos es un múltiplo de k. En caso afirmativo, intercambie los dos hijos del Node. De lo contrario, recurra para los niños izquierdo y derecho.
A continuación se muestra la implementación de la idea anterior.
C++
// c++ program swap nodes
#include<bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct Node
{
int data;
struct Node *left, *right;
};
// function to create a new tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// swap two Node
void Swap( Node **a , Node **b)
{
Node * temp = *a;
*a = *b;
*b = temp;
}
// A utility function swap left- node & right node of tree
// of every k'th level
void swapEveryKLevelUtil( Node *root, int level, int k)
{
// base case
if (root== NULL ||
(root->left==NULL && root->right==NULL) )
return ;
//if current level + 1 is present in swap vector
//then we swap left & right node
if ( (level + 1) % k == 0)
Swap(&root->left, &root->right);
// Recur for left and right subtrees
swapEveryKLevelUtil(root->left, level+1, k);
swapEveryKLevelUtil(root->right, level+1, k);
}
// This function mainly calls recursive function
// swapEveryKLevelUtil()
void swapEveryKLevel(Node *root, int k)
{
// call swapEveryKLevelUtil function with
// initial level as 1.
swapEveryKLevelUtil(root, 1, k);
}
// Utility method for inorder tree traversal
void inorder(Node *root)
{
if (root == NULL)
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
// Driver Code
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
// Java program swap nodes
class GFG
{
// A Binary Tree Node
static class Node
{
int data;
Node left, right;
};
// function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// A utility function swap left- node & right node of tree
// of every k'th level
static void swapEveryKLevelUtil( Node root, int level, int k)
{
// base case
if (root== null ||
(root.left==null && root.right==null) )
return ;
//if current level + 1 is present in swap vector
//then we swap left & right node
if ( (level + 1) % k == 0)
{
Node temp=root.left;
root.left=root.right;
root.right=temp;
}
// Recur for left and right subtrees
swapEveryKLevelUtil(root.left, level+1, k);
swapEveryKLevelUtil(root.right, level+1, k);
}
// This function mainly calls recursive function
// swapEveryKLevelUtil()
static void swapEveryKLevel(Node root, int k)
{
// call swapEveryKLevelUtil function with
// initial level as 1.
swapEveryKLevelUtil(root, 1, k);
}
// Utility method for inorder tree traversal
static void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
// Driver Code
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);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python program to swap nodes
# A binary tree node
class Node:
# constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# A utility function swap left node and right node of tree
# of every k'th level
def swapEveryKLevelUtil(root, level, k):
# Base Case
if (root is None or (root.left is None and
root.right is None ) ):
return
# If current level+1 is present in swap vector
# then we swap left and right node
if (level+1)%k == 0:
root.left, root.right = root.right, root.left
# Recur for left and right subtree
swapEveryKLevelUtil(root.left, level+1, k)
swapEveryKLevelUtil(root.right, level+1, k)
# This function mainly calls recursive function
# swapEveryKLevelUtil
def swapEveryKLevel(root, k):
# Call swapEveryKLevelUtil function with
# initial level as 1
swapEveryKLevelUtil(root, 1, k)
# Method to find the inorder tree traversal
def inorder(root):
# Base Case
if root is None:
return
inorder(root.left)
print(root.data,end=" ")
inorder(root.right)
# Driver code
"""
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)
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program swap nodes
using System;
class GFG
{
// A Binary Tree Node
public class Node
{
public int data;
public Node left, right;
};
// function to create a new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// A utility function swap left- node & right node of tree
// of every k'th level
static void swapEveryKLevelUtil( Node root, int level, int k)
{
// base case
if (root == null ||
(root.left == null && root.right==null) )
return ;
//if current level + 1 is present in swap vector
//then we swap left & right node
if ( (level + 1) % k == 0)
{
Node temp=root.left;
root.left=root.right;
root.right=temp;
}
// Recur for left and right subtrees
swapEveryKLevelUtil(root.left, level+1, k);
swapEveryKLevelUtil(root.right, level+1, k);
}
// This function mainly calls recursive function
// swapEveryKLevelUtil()
static void swapEveryKLevel(Node root, int k)
{
// call swapEveryKLevelUtil function with
// initial level as 1.
swapEveryKLevelUtil(root, 1, k);
}
// Utility method for inorder tree traversal
static void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
Console.Write(root.data + " ");
inorder(root.right);
}
// Driver Code
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);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript program swap nodes
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// function to create a new tree node
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// A utility function swap left- node & right node of tree
// of every k'th level
function swapEveryKLevelUtil(root, level, k)
{
// base case
if (root== null ||
(root.left==null && root.right==null) )
return ;
//if current level + 1 is present in swap vector
//then we swap left & right node
if ( (level + 1) % k == 0)
{
let temp=root.left;
root.left=root.right;
root.right=temp;
}
// Recur for left and right subtrees
swapEveryKLevelUtil(root.left, level+1, k);
swapEveryKLevelUtil(root.right, level+1, k);
}
// This function mainly calls recursive function
// swapEveryKLevelUtil()
function swapEveryKLevel(root, k)
{
// call swapEveryKLevelUtil function with
// initial level as 1.
swapEveryKLevelUtil(root, 1, k);
}
// Utility method for inorder tree traversal
function inorder(root)
{
if (root == null)
return;
inorder(root.left);
document.write(root.data + " ");
inorder(root.right);
}
/* 1
/ \
2 3
/ / \
4 7 8 */
let 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);
let k = 2;
document.write("Before swap node :" + "</br>");
inorder(root);
swapEveryKLevel(root, k);
document.write("</br>" + "After swap Node :" + "</br>");
inorder(root);
</script>
Producción
Before swap node : 4 2 1 7 3 8 After swap Node : 7 3 8 1 4 2
Este artículo es una contribución de Nishant_singh(pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA