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>
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