Dado un árbol binario que consiste en N Nodes y dos enteros K y L , la tarea es agregar una fila de Nodes de valor K en el nivel L , de modo que la orientación del árbol original permanezca sin cambios.
Ejemplos:
Entrada: K = 1, L = 2
Salida:
1
1 1
2 3
4 5 6
Explicación:
A continuación se muestra el árbol después de insertar el Node con valor 1 en el nivel K(= 2).Entrada: K = 1, L = 1
Salida:
1
1
2 3
4 5 6
Enfoque: El problema dado se puede resolver usando la búsqueda primero en amplitud para atravesar el árbol y agregando Nodes con un valor dado entre un Node en el nivel (L – 1) y las raíces de su subárbol izquierdo y derecho. Siga los pasos a continuación para resolver el problema:
- Si L es 1 , cree el nuevo Node con el valor K y luego únase a la raíz actual a la izquierda del nuevo Node, haciendo que el nuevo Node sea el Node raíz.
- Inicialice una cola , digamos Q , que se usa para atravesar el árbol usando BFS.
- Inicialice una variable, digamos CurrLevel que almacena el nivel actual de un Node.
- Iterar mientras Q no está vacío() y CurrLevel es menor que (L – 1) y realizar los siguientes pasos:
- Almacene el tamaño de la cola Q en una variable, digamos len .
- Iterar mientras len es mayor que 0 y luego extraer el elemento frontal de la cola y empujar el subárbol izquierdo y derecho en Q .
- Incremente el valor de CurrLevel en 1 .
- Ahora vuelva a iterar mientras Q no esté vacío() y realice los siguientes pasos:
- Almacene el Node frontal de Q en una variable, digamos temp y haga estallar el elemento frontal.
- Almacene el subárbol izquierdo y derecho del Node temporal en variables, digamos temp1 y temp2 respectivamente.
- Cree un nuevo Node con el valor K y luego únase al Node actual a la izquierda del Node temporal asignando el valor del Node a temp.left.
- De nuevo, cree un nuevo Node con el valor K y luego únase al Node actual a la derecha del Node temporal asignando el valor del Node a temp.right .
- Luego, una temp1 a la izquierda del nuevo Node, es decir, temp.left.left y temp2 a la derecha del nuevo Node, es decir, temp.right.right.
- Después de completar los pasos anteriores, imprima el árbol en un recorrido de orden de niveles .
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; // Class of TreeNode struct TreeNode { int val; TreeNode *left; TreeNode *right; // Constructor TreeNode(int v) { val = v; left = right = NULL; } }; // Function to add one row to a // binary tree TreeNode *addOneRow(TreeNode *root, int K, int L) { // If L is 1 if (L == 1) { // Store the node having // the value K TreeNode *t = new TreeNode(K); // Join node t with the // root node t->left = root; return t; } // Stores the current Level int currLevel = 1; // For performing BFS traversal queue<TreeNode*> Q; // Add root node to Queue Q Q.push(root); // Traversal while currLevel // is less than L - 1 while (Q.size() > 0 && currLevel < L - 1) { // Stores the count of the // total nodes at the // currLevel int len = Q.size(); // Iterate while len // is greater than 0 while (len > 0) { // Pop the front // element of Q TreeNode *node = Q.front(); Q.pop(); // If node.left is // not NULL if (node->left != NULL) Q.push(node->left); // If node.right is // not NULL if (node->right != NULL) Q.push(node->right); // Decrement len by 1 len--; } // Increment currLevel by 1 currLevel++; } // Iterate while Q is // non empty() while (Q.size() > 0) { // Stores the front node // of the Q queue TreeNode *temp = Q.front(); Q.pop(); // Stores its left sub-tree TreeNode *temp1 = temp->left; // Create a new Node with // value K and assign to // temp.left temp->left = new TreeNode(K); // Assign temp1 to the // temp.left.left temp->left->left = temp1; // Store its right subtree TreeNode *temp2 = temp->right; // Create a new Node with // value K and assign to // temp.right temp->right = new TreeNode(K); // Assign temp2 to the // temp.right.right temp->right->right = temp2; } // Return the updated root return root; } // Function to print the tree in // the level order traversal void levelOrder(TreeNode *root) { queue<TreeNode*> Q; if (root == NULL) { cout<<("Null")<<endl; return; } // Add root node to Q Q.push(root); while (Q.size() > 0) { // Stores the total nodes // at current level int len = Q.size(); // Iterate while len // is greater than 0 while (len > 0) { // Stores the front Node TreeNode *temp = Q.front(); Q.pop(); // Print the value of // the current node cout << temp->val << " "; // If reference to left // subtree is not NULL if (temp->left != NULL) // Add root of left // subtree to Q Q.push(temp->left); // If reference to right // subtree is not NULL if (temp->right != NULL) // Add root of right // subtree to Q Q.push(temp->right); // Decrement len by 1 len--; } cout << endl; } } // Driver Code int main() { // Given Tree TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right = new TreeNode(3); root->right->right = new TreeNode(6); int L = 2; int K = 1; levelOrder(addOneRow(root, K, L)); } // This code is contributed by mohit kumar 29.
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Class of TreeNode public static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} // Constructor TreeNode(int val) { this.val = val; } } // Function to add one row to a // binary tree public static TreeNode addOneRow( TreeNode root, int K, int L) { // If L is 1 if (L == 1) { // Store the node having // the value K TreeNode t = new TreeNode(K); // Join node t with the // root node t.left = root; return t; } // Stores the current Level int currLevel = 1; // For performing BFS traversal Queue<TreeNode> Q = new LinkedList<TreeNode>(); // Add root node to Queue Q Q.add(root); // Traversal while currLevel // is less than L - 1 while (!Q.isEmpty() && currLevel < L - 1) { // Stores the count of the // total nodes at the // currLevel int len = Q.size(); // Iterate while len // is greater than 0 while (len > 0) { // Pop the front // element of Q TreeNode node = Q.poll(); // If node.left is // not null if (node.left != null) Q.add(node.left); // If node.right is // not null if (node.right != null) Q.add(node.right); // Decrement len by 1 len--; } // Increment currLevel by 1 currLevel++; } // Iterate while Q is // non empty() while (!Q.isEmpty()) { // Stores the front node // of the Q queue TreeNode temp = Q.poll(); // Stores its left sub-tree TreeNode temp1 = temp.left; // Create a new Node with // value K and assign to // temp.left temp.left = new TreeNode(K); // Assign temp1 to the // temp.left.left temp.left.left = temp1; // Store its right subtree TreeNode temp2 = temp.right; // Create a new Node with // value K and assign to // temp.right temp.right = new TreeNode(K); // Assign temp2 to the // temp.right.right temp.right.right = temp2; } // Return the updated root return root; } // Function to print the tree in // the level order traversal public static void levelOrder( TreeNode root) { Queue<TreeNode> Q = new LinkedList<>(); if (root == null) { System.out.println("Null"); return; } // Add root node to Q Q.add(root); while (!Q.isEmpty()) { // Stores the total nodes // at current level int len = Q.size(); // Iterate while len // is greater than 0 while (len > 0) { // Stores the front Node TreeNode temp = Q.poll(); // Print the value of // the current node System.out.print( temp.val + " "); // If reference to left // subtree is not null if (temp.left != null) // Add root of left // subtree to Q Q.add(temp.left); // If reference to right // subtree is not null if (temp.right != null) // Add root of right // subtree to Q Q.add(temp.right); // Decrement len by 1 len--; } System.out.println(); } } // Driver Code public static void main(String[] args) { // Given Tree TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right = new TreeNode(3); root.right.right = new TreeNode(6); int L = 2; int K = 1; levelOrder(addOneRow(root, K, L)); } }
Python3
# Python program for the above approach # Class of TreeNode class TreeNode: def __init__(self, val): self.val = val self.left,self.right = None,None # Function to add one row to a # binary tree def addOneRow(root,K,L): # If L is 1 if (L == 1): # Store the node having # the value K t = TreeNode(K) # Join node t with the # root node t.left = root return t # Stores the current Level currLevel = 1 # For performing BFS traversal Q =[] # Add root node to Queue Q Q.append(root) # Traversal while currLevel # is less than L - 1 while (len(Q)!=0 and currLevel < L - 1): # Stores the count of the # total nodes at the # currLevel Len = len(Q) # Iterate while len # is greater than 0 while (Len > 0): # Pop the front # element of Q node = Q[0] Q = Q[1:] # If node.left is # not None if (node.left != None): Q.append(node.left) # If node.right is # not None if (node.right != None): Q.append(node.right) # Decrement len by 1 Len -= 1 # Increment currLevel by 1 currLevel += 1 # Iterate while Q is # non empty() while (len(Q)!=0): # Stores the front node # of the Q queue temp = Q[0] Q = Q[1:] # Stores its left sub-tree temp1 = temp.left # Create a Node with # value K and assign to # temp.left temp.left = TreeNode(K) # Assign temp1 to the # temp.left.left temp.left.left = temp1 # Store its right subtree temp2 = temp.right # Create a Node with # value K and assign to # temp.right temp.right = TreeNode(K) # Assign temp2 to the # temp.right.right temp.right.right = temp2 # Return the updated root return root # Function to print the tree in # the level order traversal def levelOrder(root): Q = [] if (root == None): print("Null") return # Add root node to Q Q.append(root) while (len(Q)!=0): # Stores the total nodes # at current level Len = len(Q) # Iterate while len # is greater than 0 while (Len > 0): # Stores the front Node temp = Q[0] Q = Q[1:] # Print the value of # the current node print(temp.val,end=" ") # If reference to left # subtree is not null if (temp.left != None): # Add root of left # subtree to Q Q.append(temp.left) # If reference to right # subtree is not null if (temp.right != None): # Add root of right # subtree to Q Q.append(temp.right) # Decrement len by 1 Len -= 1 print() # Driver Code root = TreeNode(1) root.left = TreeNode(2) root.left.left = TreeNode(4) root.left.right = TreeNode(5) root.right = TreeNode(3) root.right.right = TreeNode(6) L = 2 K = 1 levelOrder(addOneRow(root, K, L)) # This code is contributed by shinjanpatra
Javascript
<script> // JavaScript program for the above approach // Class of TreeNode class TreeNode { constructor(val) { this.val=val; this.left=this.right=null; } } // Function to add one row to a // binary tree function addOneRow(root,K,L) { // If L is 1 if (L == 1) { // Store the node having // the value K let t = new TreeNode(K); // Join node t with the // root node t.left = root; return t; } // Stores the current Level let currLevel = 1; // For performing BFS traversal let Q =[]; // Add root node to Queue Q Q.push(root); // Traversal while currLevel // is less than L - 1 while (Q.length!=0 && currLevel < L - 1) { // Stores the count of the // total nodes at the // currLevel let len = Q.length; // Iterate while len // is greater than 0 while (len > 0) { // Pop the front // element of Q let node = Q.shift(); // If node.left is // not null if (node.left != null) Q.push(node.left); // If node.right is // not null if (node.right != null) Q.push(node.right); // Decrement len by 1 len--; } // Increment currLevel by 1 currLevel++; } // Iterate while Q is // non empty() while (Q.length!=0) { // Stores the front node // of the Q queue let temp = Q.shift(); // Stores its left sub-tree let temp1 = temp.left; // Create a new Node with // value K and assign to // temp.left temp.left = new TreeNode(K); // Assign temp1 to the // temp.left.left temp.left.left = temp1; // Store its right subtree let temp2 = temp.right; // Create a new Node with // value K and assign to // temp.right temp.right = new TreeNode(K); // Assign temp2 to the // temp.right.right temp.right.right = temp2; } // Return the updated root return root; } // Function to print the tree in // the level order traversal function levelOrder(root) { let Q= []; if (root == null) { document.write("Null<br>"); return; } // Add root node to Q Q.push(root); while (Q.length!=0) { // Stores the total nodes // at current level let len = Q.length; // Iterate while len // is greater than 0 while (len > 0) { // Stores the front Node let temp = Q.shift(); // Print the value of // the current node document.write( temp.val + " "); // If reference to left // subtree is not null if (temp.left != null) // Add root of left // subtree to Q Q.push(temp.left); // If reference to right // subtree is not null if (temp.right != null) // Add root of right // subtree to Q Q.push(temp.right); // Decrement len by 1 len--; } document.write("<br>"); } } // Driver Code let root = new TreeNode(1); root.left = new TreeNode(2); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right = new TreeNode(3); root.right.right = new TreeNode(6); let L = 2; let K = 1; levelOrder(addOneRow(root, K, L)); // This code is contributed by unknown2108 </script>
1 1 1 2 3 4 5 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por gireeshgudaparthi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA