Gire a la izquierda los dígitos de los valores de Node de todos los niveles de un árbol binario en orden creciente

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 15

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *