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>
Producción:
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