Dado un árbol binario , la tarea es reemplazar el valor de cada Node con la suma de todos los Nodes presentes en el mismo nivel.
Ejemplos:
Aporte:
9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8Producción:
9 / \ 16 16 / \ \ 22 22 22 / \ \ 16 16 16Explicación:
La suma de los Nodes en el nivel 1: 9
La suma de los Nodes en el nivel 2: 6 + 10 = 16
La suma de los Nodes en el nivel 3: 4 + 7 + 11 = 22
La suma de los Nodes en el nivel 4: 3 + 5 + 8 = 16
Aporte:
5 / \ 6 3 / \ \ 4 9 2Producción:
5 / \ 9 9 / \ \ 15 15 15
Enfoque: La idea de encontrar la suma de los Nodes en cada nivel del Árbol y reemplazar cada Node con la suma de los Nodes en ese nivel usando Level Order Traversal . Siga los pasos a continuación para resolver el problema:
- Inicialice dos colas , digamos que1 y que2 , donde la suma de los Nodes en cada nivel se puede calcular usando que1 y reemplace cada Node con la suma de todos los Nodes en el mismo nivel usando que2 .
- Use Level Order Traversal y calcule la suma de todos los Nodes en cada nivel del árbol.
- Use Level Order Traversal y reemplace cada Node con la suma de todos los Nodes en ese nivel del árbol.
- Finalmente, imprima el árbol usando Level Order Traversal .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of the binary tree
struct TreeNode
{
int val = 0;
TreeNode *left,*right;
TreeNode(int x)
{
val = x;
left = NULL;
right = NULL;
}
};
// Function to replace each node of the tree
// with the sum of nodes in the same level
TreeNode* replaceLvl(TreeNode *root){
// If root is null
if (!root)
return root;
// Queue to store nodes
// of each level of the Tree
queue<TreeNode*> que1;
queue<TreeNode*> que2;
que1.push(root);
que2.push(root);
while (true)
{
// Stores length of que1
int lenque1 = que1.size();
// Stores length of que2
int lenque2 = que2.size();
// Stores sum of nodes at
// each level of the tree
int lvlsum = 0;
if (lenque1 == 0)
break;
// Traverse the tree and store
// the sum at each level
while (lenque1 > 0)
{
// Stores the front element
// of the queue
auto temp = que1.front();
que1.pop();
// Update lvlsum
lvlsum += temp->val;
// If left subtree not null
if (temp->left)
que1.push(temp->left);
// If right subtree not null
if (temp->right)
que1.push(temp->right);
// Update lenque1
lenque1 -= 1;
}
// Replace all the nodes of at
// each level of the tree
while (lenque2 > 0)
{
// Stores front element
// of the queue
auto temp = que2.front();
que2.pop();
// Replace current node with
// the sum of nodes
temp->val = lvlsum;
// If left subtree is not null
if (temp->left)
que2.push(temp->left);
// If right subtree is not null
if (temp->right)
que2.push(temp->right);
// Update lenque2
lenque2 -= 1;
}
}
return root;
}
// Function to print level order
// traversal of the Binary Tree
void printLvl(TreeNode *root)
{
// Push root node into queue
queue<TreeNode*> que;
que.push(root);
while (true)
{
// Stores count of nodes
// at each level
int length = que.size();
// If no nodes left
if (length == 0)
break;
while (length)
{
//Stores front element
// of the queue
auto temp = que.front();
que.pop();
cout << temp->val << " ";
// If left subtree is not null
if (temp->left)
que.push(temp->left);
// If right subtree is not null
if (temp->right)
que.push(temp->right);
// Update length
length -= 1;
}
cout << endl;
}
}
// Driver Code
int main()
{
TreeNode *root = new TreeNode(4);
root->left = new TreeNode(5);
root->right = new TreeNode(7);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right->right = new TreeNode(5);
// To update the tree
root = replaceLvl(root);
// To display the updated tree
printLvl(root);
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
class GFG
{
// Structure of a Node
static class TreeNode
{
int val;
TreeNode left, right;
TreeNode(int key)
{
val = key;
left = null;
right = null;
}
};
// Function to replace each node of the tree
// with the sum of nodes in the same level
static TreeNode replaceLvl(TreeNode root){
// If root is null
if (root==null)
return root;
// Queue to store nodes
// of each level of the Tree
Queue<TreeNode> que1=new LinkedList<>();
Queue<TreeNode> que2=new LinkedList<>();
que1.add(root);
que2.add(root);
while (true)
{
// Stores length of que1
int lenque1 = que1.size();
// Stores length of que2
int lenque2 = que2.size();
// Stores sum of nodes at
// each level of the tree
int lvlsum = 0;
if (lenque1 == 0)
break;
// Traverse the tree and store
// the sum at each level
while (lenque1 > 0)
{
// Stores the front element
// of the queue
TreeNode temp = que1.peek();
que1.poll();
// Update lvlsum
lvlsum += temp.val;
// If left subtree not null
if (temp.left!=null)
que1.add(temp.left);
// If right subtree not null
if (temp.right!=null)
que1.add(temp.right);
// Update lenque1
lenque1 -= 1;
}
// Replace all the nodes of at
// each level of the tree
while (lenque2 > 0)
{
// Stores front element
// of the queue
TreeNode temp = que2.peek();
que2.poll();
// Replace current node with
// the sum of nodes
temp.val = lvlsum;
// If left subtree is not null
if (temp.left!=null)
que2.add(temp.left);
// If right subtree is not null
if (temp.right!=null)
que2.add(temp.right);
// Update lenque2
lenque2 -= 1;
}
}
return root;
}
// Function to print level order
// traversal of the Binary Tree
static void printLvl(TreeNode root)
{
// Push root node into queue
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
while (true)
{
// Stores count of nodes
// at each level
int length = que.size();
// If no nodes left
if (length == 0)
break;
while (length>0)
{
//Stores front element
// of the queue
TreeNode temp = que.peek();
que.poll();
System.out.print(temp.val+" ");
// If left subtree is not null
if (temp.left != null)
que.add(temp.left);
// If right subtree is not null
if (temp.right != null)
que.add(temp.right);
// Update length
length -= 1;
}
System.out.println();
}
}
// Driver function
public static void main (String[] args) {
TreeNode root = new TreeNode(4);
root.left = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right = new TreeNode(7);
root.right.right = new TreeNode(5);
// To update the tree
root = replaceLvl(root);
// To display the updated tree
printLvl(root);
}
}
// This code is contributed by offbeat
Python3
# Python program to implement # the above approach # Structure of the binary tree class TreeNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right # Function to replace each node of the tree # with the sum of nodes in the same level def replaceLvl(root): # If root is null if not root: return # Queue to store nodes # of each level of the Tree que1 = [root] que2 = [root] while True: # Stores length of que1 lenque1 = len(que1) # Stores length of que2 lenque2 = len(que2) # Stores sum of nodes at # each level of the tree lvlsum = 0 if not lenque1: break # Traverse the tree and store # the sum at each level while lenque1: # Stores the front element # of the queue temp = que1.pop(0) # Update lvlsum lvlsum += temp.val # If left subtree not null if temp.left: que1.append(temp.left) # If right subtree not null if temp.right: que1.append(temp.right) # Update lenque1 lenque1 -= 1 # Replace all the nodes of at # each level of the tree while lenque2: # Stores front element # of the queue temp = que2.pop(0) # Replace current node with # the sum of nodes temp.val = lvlsum # If left subtree is not null if temp.left: que2.append(temp.left) # If right subtree is not null if temp.right: que2.append(temp.right) # Update lenque2 lenque2 -= 1 return root # Function to print level order # traversal of the Binary Tree def printLvl(root): # Push root node into queue que = [root] while True: # Stores count of nodes # at each level length = len(que) # If no nodes left if not length: break while length: # Stores front element # of the queue temp = que.pop(0) print(temp.val, end =' ') # If left subtree is not null if temp.left: que.append(temp.left) # If right subtree is not null if temp.right: que.append(temp.right) # Update length length -= 1 print() # Driver Code root = TreeNode(4) root.left = TreeNode(5) root.right = TreeNode(7) root.left.left = TreeNode(1) root.left.right = TreeNode(3) root.right.right = TreeNode(5) # To update the tree root = replaceLvl(root) # To display the updated tree printLvl(root)
C#
// C# program for above approach
using System;
using System.Collections.Generic;
public class TreeNode
{
public int val;
public TreeNode left, right;
public TreeNode(int key)
{
val = key;
left = null;
right = null;
}
}
public class GFG{
// Function to replace each node of the tree
// with the sum of nodes in the same level
static TreeNode replaceLvl(TreeNode root){
// If root is null
if (root==null)
return root;
// Queue to store nodes
// of each level of the Tree
Queue<TreeNode> que1=new Queue<TreeNode>();
Queue<TreeNode> que2=new Queue<TreeNode>();
que1.Enqueue(root);
que2.Enqueue(root);
while (true)
{
// Stores length of que1
int lenque1 = que1.Count;
// Stores length of que2
int lenque2 = que2.Count;
// Stores sum of nodes at
// each level of the tree
int lvlsum = 0;
if (lenque1 == 0)
break;
// Traverse the tree and store
// the sum at each level
while (lenque1 > 0)
{
// Stores the front element
// of the queue
TreeNode temp = que1.Dequeue();
// Update lvlsum
lvlsum += temp.val;
// If left subtree not null
if (temp.left!=null)
que1.Enqueue(temp.left);
// If right subtree not null
if (temp.right!=null)
que1.Enqueue(temp.right);
// Update lenque1
lenque1 -= 1;
}
// Replace all the nodes of at
// each level of the tree
while (lenque2 > 0)
{
// Stores front element
// of the queue
TreeNode temp = que2.Dequeue();
// Replace current node with
// the sum of nodes
temp.val = lvlsum;
// If left subtree is not null
if (temp.left!=null)
que2.Enqueue(temp.left);
// If right subtree is not null
if (temp.right!=null)
que2.Enqueue(temp.right);
// Update lenque2
lenque2 -= 1;
}
}
return root;
}
// Function to print level order
// traversal of the Binary Tree
static void printLvl(TreeNode root)
{
// Push root node into queue
Queue<TreeNode> que = new Queue<TreeNode>();
que.Enqueue(root);
while (true)
{
// Stores count of nodes
// at each level
int length = que.Count;
// If no nodes left
if (length == 0)
break;
while (length>0)
{
//Stores front element
// of the queue
TreeNode temp = que.Dequeue();
Console.Write(temp.val+" ");
// If left subtree is not null
if (temp.left != null)
que.Enqueue(temp.left);
// If right subtree is not null
if (temp.right != null)
que.Enqueue(temp.right);
// Update length
length -= 1;
}
Console.WriteLine();
}
}
// Driver function
static public void Main (){
TreeNode root = new TreeNode(4);
root.left = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right = new TreeNode(7);
root.right.right = new TreeNode(5);
// To update the tree
root = replaceLvl(root);
// To display the updated tree
printLvl(root);
}
}
// This code is contributed by patel2127
Javascript
<script>
// JavaScript program for above approach
// Structure of a Node
class TreeNode
{
constructor(key) {
this.left = null;
this.right = null;
this.val = key;
}
}
// Function to replace each node of the tree
// with the sum of nodes in the same level
function replaceLvl(root){
// If root is null
if (root==null)
return root;
// Queue to store nodes
// of each level of the Tree
let que1 = [];
let que2 = [];
que1.push(root);
que2.push(root);
while (true)
{
// Stores length of que1
let lenque1 = que1.length;
// Stores length of que2
let lenque2 = que2.length;
// Stores sum of nodes at
// each level of the tree
let lvlsum = 0;
if (lenque1 == 0)
break;
// Traverse the tree and store
// the sum at each level
while (lenque1 > 0)
{
// Stores the front element
// of the queue
let temp = que1[0];
que1.shift();
// Update lvlsum
lvlsum += temp.val;
// If left subtree not null
if (temp.left!=null)
que1.push(temp.left);
// If right subtree not null
if (temp.right!=null)
que1.push(temp.right);
// Update lenque1
lenque1 -= 1;
}
// Replace all the nodes of at
// each level of the tree
while (lenque2 > 0)
{
// Stores front element
// of the queue
let temp = que2[0];
que2.shift();
// Replace current node with
// the sum of nodes
temp.val = lvlsum;
// If left subtree is not null
if (temp.left!=null)
que2.push(temp.left);
// If right subtree is not null
if (temp.right!=null)
que2.push(temp.right);
// Update lenque2
lenque2 -= 1;
}
}
return root;
}
// Function to print level order
// traversal of the Binary Tree
function printLvl(root)
{
// Push root node into queue
let que = [];
que.push(root);
while (true)
{
// Stores count of nodes
// at each level
let length = que.length;
// If no nodes left
if (length == 0)
break;
while (length>0)
{
//Stores front element
// of the queue
let temp = que[0];
que.shift();
document.write(temp.val+" ");
// If left subtree is not null
if (temp.left != null)
que.push(temp.left);
// If right subtree is not null
if (temp.right != null)
que.push(temp.right);
// Update length
length -= 1;
}
document.write("</br>");
}
}
let root = new TreeNode(4);
root.left = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right = new TreeNode(7);
root.right.right = new TreeNode(5);
// To update the tree
root = replaceLvl(root);
// To display the updated tree
printLvl(root);
</script>
Producción:
4 12 12 9 9 9
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