Modifique un árbol binario agregando un nivel de Nodes con un valor dado en un nivel específico

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

Deja una respuesta

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