Dado un árbol binario , la tarea es modificar el árbol girando a la izquierda cada Node cualquier número de veces, de modo que cada nivel consista en valores de Node en orden creciente de izquierda a derecha. Si no es posible organizar los valores de los Nodes de cualquier nivel en orden creciente, imprima «-1» .
Ejemplos:
Entrada:
341
/ \
241 123
/ \ \
324 235 161
Salida:
341
/ \
124 231
/ \ \
243 352 611
Explicación:
Nivel 1: El valor del Node raíz es 341, teniendo todos los dígitos ordenados.
Nivel 2: Los valores de los Nodes son 241 y 123. Girar a la izquierda 241 dos veces y 231 una vez modifica los valores de los Nodes a 124 y 231.
Nivel 3:Los valores de Node son 342, 235 y 161. Los dígitos giratorios a la izquierda de 342 una vez, 235 una vez y 161 una vez modifican los valores de Node a {243, 352, 611} respectivamente.Entrada:
12
/ \
89 15Salida: -1
Enfoque: el problema dado se puede resolver realizando un recorrido de orden de niveles y rotando a la izquierda los dígitos de los valores de los Nodes para hacer valores en cada nivel en orden creciente. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola , digamos Q , que se usa para realizar el recorrido de orden de nivel.
- Empuje el Node raíz del árbol en la cola .
- Iterar hasta que la cola no esté vacía y realizar los siguientes pasos:
- Encuentre el tamaño de la cola y guárdelo en la variable L .
- Inicialice una variable, digamos anterior , que se usa para almacenar el elemento anterior en el nivel actual del árbol.
- Iterar sobre el rango [0, L] y realizar los siguientes pasos:
- Abre el Node frontal de la cola y guárdalo en una variable, digamos temp .
- Ahora, cambie a la izquierda la temperatura del elemento y, si existe alguna permutación que sea mayor que la anterior y más cercana a la anterior , actualice el valor del Node actual como el valor de la temperatura .
- Actualice el valor de prev al valor actual de temp .
- Si el temporal tiene un hijo izquierdo o derecho, entonces empújelo a la cola.
- Después de los pasos anteriores, si el conjunto actual de Nodes no se ordenó en orden creciente, imprima «No» . De lo contrario, verifique la próxima iteración.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// TreeNode class
struct TreeNode
{
int val;
TreeNode* left,*right;
TreeNode(int v)
{
val = v;
left = NULL;
right = NULL;
}
};
// Function to check if the nodes
// are in increasing order or not
bool isInc(TreeNode *root)
{
// Perform Level Order Traversal
queue<TreeNode*> que;
que.push(root);
while (true)
{
// Current length of queue
int length = que.size();
// If queue is empty
if (length == 0)
break;
auto pre = que.front();
// Level order traversal
while (length > 0)
{
// Pop element from
// front of the queue
auto temp = que.front();
que.pop();
// If previous value exceeds
// current value, return false
if (pre->val > temp->val)
return false;
pre = temp;
if (temp->left)
que.push(temp->left);
if (temp->right)
que.push(temp->right);
length -= 1;
}
}
return true;
}
// Function to print the Tree
// after modification
void levelOrder(TreeNode *root)
{
// Performs level
// order traversal
queue<TreeNode*> que;
que.push(root);
while (true)
{
// Calculate size of the queue
int length = que.size();
if (length == 0)
break;
// Iterate until queue is empty
while (length)
{
auto temp = que.front();
que.pop();
cout << temp->val << " ";
if (temp->left)
que.push(temp->left);
if (temp->right)
que.push(temp->right);
length -= 1;
}
cout << endl;
}
cout << endl;
}
// Function to arrange node values
// of each level in increasing order
void makeInc(TreeNode *root)
{
// Perform level order traversal
queue<TreeNode*> que;
que.push(root);
while (true)
{
// Calculate length of queue
int length = que.size();
// If queue is empty
if (length == 0)
break;
int prev = -1;
// Level order traversal
while (length > 0)
{
//cout<<"loop";
// Pop element from
// front of the queue
auto temp = que.front();
que.pop();
// Initialize the optimal
// element by the initial
// element
auto optEle = temp->val;
auto strEle = to_string(temp->val);
// Check for all left
// shift operations
bool flag = true;
int yy = strEle.size();
for(int idx = 0; idx < strEle.size(); idx++)
{
// Left shift
int ls = stoi(strEle.substr(idx, yy) +
strEle.substr(0, idx));
if (ls >= prev and flag)
{
optEle = ls;
flag = false;
}
// If the current shifting
// gives optimal solution
if (ls >= prev)
optEle = min(optEle, ls);
}
// Replacing initial element
// by the optimal element
temp->val = optEle;
prev = temp->val;
// Push the LST
if (temp->left)
que.push(temp->left);
// Push the RST
if (temp->right)
que.push(temp->right);
length -= 1;
}
}
// Print the result
if (isInc(root))
levelOrder(root);
else
cout << (-1);
}
// Driver Code
int main()
{
TreeNode *root = new TreeNode(341);
root->left = new TreeNode(241);
root->right = new TreeNode(123);
root->left->left = new TreeNode(324);
root->left->right = new TreeNode(235);
root->right->right = new TreeNode(161);
makeInc(root);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
class GFG{
// TreeNode class
static class TreeNode
{
public int val;
public TreeNode left,right;
};
static TreeNode newNode(int v)
{
TreeNode temp = new TreeNode();
temp.val = v;
temp.left = temp.right = null;
return temp;
}
// Function to check if the nodes
// are in increasing order or not
static boolean isInc(TreeNode root)
{
// Perform Level Order Traversal
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (true)
{
// Current len of queue
int len = que.size();
// If queue is empty
if (len == 0)
break;
TreeNode pre = que.peek();
// Level order traversal
while (len > 0)
{
// Pop element from
// front of the queue
TreeNode temp = que.peek();
que.poll();
// If previous value exceeds
// current value, return false
if (pre.val > temp.val)
return false;
pre = temp;
if (temp.left != null)
que.add(temp.left);
if (temp.right != null)
que.add(temp.right);
len -= 1;
}
}
return true;
}
// Function to print the Tree
// after modification
static void levelOrder(TreeNode root)
{
// Performs level
// order traversal
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (true)
{
// Calculate size of the queue
int len = que.size();
if (len == 0)
break;
// Iterate until queue is empty
while (len > 0)
{
TreeNode temp = que.peek();
que.poll();
System.out.print(temp.val+" ");
if (temp.left != null)
que.add(temp.left);
if (temp.right != null)
que.add(temp.right);
len -= 1;
}
System.out.println();
}
System.out.println();
}
// Function to arrange node values
// of each level in increasing order
static void makeInc(TreeNode root)
{
// Perform level order traversal
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (true)
{
// Calculate len of queue
int len = que.size();
// If queue is empty
if (len == 0)
break;
int prev = -1;
// Level order traversal
while (len > 0)
{
//cout<<"loop";
// Pop element from
// front of the queue
TreeNode temp = que.peek();
que.poll();
// Initialize the optimal
// element by the initial
// element
int optEle = temp.val;
String strEle = String.valueOf(optEle);
// Check for all left
// shift operations
boolean flag = true;
int yy = strEle.length();
for(int idx = 0; idx < strEle.length(); idx++)
{
// Left shift
String s1 = strEle.substring(idx, yy);
String s2 = strEle.substring(0, idx);
String s = s1+ s2;
int ls = Integer.valueOf(s);
if (ls >= prev && flag)
{
optEle = ls;
flag = false;
}
// If the current shifting
// gives optimal solution
if (ls >= prev)
optEle = Math.min(optEle, ls);
}
// Replacing initial element
// by the optimal element
temp.val = optEle;
prev = temp.val;
// Push the LST
if (temp.left != null)
que.add(temp.left);
// Push the RST
if (temp.right != null)
que.add(temp.right);
len -= 1;
}
}
// Print the result
if (isInc(root) == true)
levelOrder(root);
else
System.out.print(-1);
}
// Driver code
public static void main (String[] args)
{
TreeNode root = newNode(341);
root.left = newNode(241);
root.right = newNode(123);
root.left.left = newNode(324);
root.left.right = newNode(235);
root.right.right = newNode(161);
makeInc(root);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # TreeNode class class TreeNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right # Function to check if the nodes # are in increasing order or not def isInc(root): # Perform Level Order Traversal que = [root] while True: # Current length of queue length = len(que) # If queue is empty if not length: break pre = que[0] # Level order traversal while length: # Pop element from # front of the queue temp = que.pop(0) # If previous value exceeds # current value, return false if pre.val > temp.val: return False pre = temp if temp.left: que.append(temp.left) if temp.right: que.append(temp.right) length -= 1 return True # Function to arrange node values # of each level in increasing order def makeInc(root): # Perform level order traversal que = [root] while True: # Calculate length of queue length = len(que) # If queue is empty if not length: break prev = -1 # Level order traversal while length: # Pop element from # front of the queue temp = que.pop(0) # Initialize the optimal # element by the initial # element optEle = temp.val strEle = str(temp.val) # Check for all left # shift operations flag = True for idx in range(len(strEle)): # Left shift ls = int(strEle[idx:] + strEle[:idx]) if ls >= prev and flag: optEle = ls flag = False # If the current shifting # gives optimal solution if ls >= prev: optEle = min(optEle, ls) # Replacing initial element # by the optimal element temp.val = optEle prev = temp.val # Push the LST if temp.left: que.append(temp.left) # Push the RST if temp.right: que.append(temp.right) length -= 1 # Print the result if isInc(root): levelOrder(root) else: print(-1) # Function to print the Tree # after modification def levelOrder(root): # Performs level # order traversal que = [root] while True: # Calculate size of the queue length = len(que) if not length: break # Iterate until queue is empty while length: temp = que.pop(0) print(temp.val, end =' ') if temp.left: que.append(temp.left) if temp.right: que.append(temp.right) length -= 1 print() # Driver Code root = TreeNode(341) root.left = TreeNode(241) root.right = TreeNode(123) root.left.left = TreeNode(324) root.left.right = TreeNode(235) root.right.right = TreeNode(161) makeInc(root)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// TreeNode class
class TreeNode
{
public int val;
public TreeNode left,right;
};
static TreeNode newNode(int v)
{
TreeNode temp = new TreeNode();
temp.val = v;
temp.left = temp.right = null;
return temp;
}
// Function to check if the nodes
// are in increasing order or not
static bool isInc(TreeNode root)
{
// Perform Level Order Traversal
Queue<TreeNode> que = new Queue<TreeNode>();
que.Enqueue(root);
while (true)
{
// Current len of queue
int len = que.Count;
// If queue is empty
if (len == 0)
break;
TreeNode pre = que.Peek();
// Level order traversal
while (len > 0)
{
// Pop element from
// front of the queue
TreeNode temp = que.Peek();
que.Dequeue();
// If previous value exceeds
// current value, return false
if (pre.val > temp.val)
return false;
pre = temp;
if (temp.left != null)
que.Enqueue(temp.left);
if (temp.right != null)
que.Enqueue(temp.right);
len -= 1;
}
}
return true;
}
// Function to print the Tree
// after modification
static void levelOrder(TreeNode root)
{
// Performs level
// order traversal
Queue<TreeNode> que = new Queue<TreeNode>();
que.Enqueue(root);
while (true)
{
// Calculate size of the queue
int len = que.Count;
if (len == 0)
break;
// Iterate until queue is empty
while (len > 0)
{
TreeNode temp = que.Peek();
que.Dequeue();
Console.Write(temp.val+" ");
if (temp.left != null)
que.Enqueue(temp.left);
if (temp.right != null)
que.Enqueue(temp.right);
len -= 1;
}
Console.Write("\n");
}
Console.Write("\n");
}
// Function to arrange node values
// of each level in increasing order
static void makeInc(TreeNode root)
{
// Perform level order traversal
Queue<TreeNode> que = new Queue<TreeNode>();
que.Enqueue(root);
while (true)
{
// Calculate len of queue
int len = que.Count;
// If queue is empty
if (len == 0)
break;
int prev = -1;
// Level order traversal
while (len > 0)
{
//cout<<"loop";
// Pop element from
// front of the queue
TreeNode temp = que.Peek();
que.Dequeue();
// Initialize the optimal
// element by the initial
// element
int optEle = temp.val;
string strEle = optEle.ToString();
// Check for all left
// shift operations
bool flag = true;
int yy = strEle.Length;
for(int idx = 0; idx < strEle.Length; idx++)
{
// Left shift
string s1 = strEle.Substring(idx, yy - idx);
string s2 = strEle.Substring(0, idx);
string s = String.Concat(s1, s2);
int ls = Int32.Parse(s);
if (ls >= prev && flag)
{
optEle = ls;
flag = false;
}
// If the current shifting
// gives optimal solution
if (ls >= prev)
optEle = Math.Min(optEle, ls);
}
// Replacing initial element
// by the optimal element
temp.val = optEle;
prev = temp.val;
// Push the LST
if (temp.left != null)
que.Enqueue(temp.left);
// Push the RST
if (temp.right != null)
que.Enqueue(temp.right);
len -= 1;
}
}
// Print the result
if (isInc(root) == true)
levelOrder(root);
else
Console.Write(-1);
}
// Driver Code
public static void Main()
{
TreeNode root = newNode(341);
root.left = newNode(241);
root.right = newNode(123);
root.left.left = newNode(324);
root.left.right = newNode(235);
root.right.right = newNode(161);
makeInc(root);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for the above approach
// TreeNode class
class Node
{
constructor(v)
{
this.val=v;
this.left=this.right=null;
}
}
// Function to check if the nodes
// are in increasing order or not
function isInc(root)
{
// Perform Level Order Traversal
let que = [];
que.push(root);
while (true)
{
// Current len of queue
let len = que.length;
// If queue is empty
if (len == 0)
break;
let pre = que[0];
// Level order traversal
while (len > 0)
{
// Pop element from
// front of the queue
let temp = que[0];
que.shift();
// If previous value exceeds
// current value, return false
if (pre.val > temp.val)
return false;
pre = temp;
if (temp.left != null)
que.push(temp.left);
if (temp.right != null)
que.push(temp.right);
len -= 1;
}
}
return true;
}
// Function to print the Tree
// after modification
function levelOrder(root)
{
// Performs level
// order traversal
let que = [];
que.push(root);
while (true)
{
// Calculate size of the queue
let len = que.length;
if (len == 0)
break;
// Iterate until queue is empty
while (len > 0)
{
let temp = que[0];
que.shift();
document.write(temp.val+" ");
if (temp.left != null)
que.push(temp.left);
if (temp.right != null)
que.push(temp.right);
len -= 1;
}
document.write("<br>");
}
document.write("<br>");
}
// Function to arrange node values
// of each level in increasing order
function makeInc(root)
{
// Perform level order traversal
let que = [];
que.push(root);
while (true)
{
// Calculate len of queue
let len = que.length;
// If queue is empty
if (len == 0)
break;
let prev = -1;
// Level order traversal
while (len > 0)
{
//cout<<"loop";
// Pop element from
// front of the queue
let temp = que[0];
que.shift();
// Initialize the optimal
// element by the initial
// element
let optEle = temp.val;
let strEle = (optEle).toString();
// Check for all left
// shift operations
let flag = true;
let yy = strEle.length;
for(let idx = 0; idx < strEle.length; idx++)
{
// Left shift
let s1 = strEle.substring(idx, yy);
let s2 = strEle.substring(0, idx);
let s = s1+ s2;
let ls = parseInt(s);
if (ls >= prev && flag)
{
optEle = ls;
flag = false;
}
// If the current shifting
// gives optimal solution
if (ls >= prev)
optEle = Math.min(optEle, ls);
}
// Replacing initial element
// by the optimal element
temp.val = optEle;
prev = temp.val;
// Push the LST
if (temp.left != null)
que.push(temp.left);
// Push the RST
if (temp.right != null)
que.push(temp.right);
len -= 1;
}
}
// Print the result
if (isInc(root) == true)
levelOrder(root);
else
document.write(-1);
}
// Driver code
let root = new Node(341);
root.left = new Node(241);
root.right = new Node(123);
root.left.left = new Node(324);
root.left.right = new Node(235);
root.right.right = new Node(161);
makeInc(root);
// This code is contributed by patel2127
</script>
Producción:
134 124 231 243 352 611
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA