Dado un árbol binario, la tarea es imprimir la suma de los Nodes en la vista inferior del árbol binario dado. La vista inferior de un árbol binario es el conjunto de Nodes visibles cuando el árbol se ve desde abajo.
Ejemplos:
Input :
1
/ \
2 3
/ \ \
4 5 6
Output : 20
Input :
1
/ \
2 3
\
4
\
5
\
6
Output : 17
Enfoque: La idea es utilizar una cola.
- Coloque los Nodes del árbol en una cola para el recorrido del orden de niveles
- Comience con la distancia horizontal (hd) 0 del Node raíz, siga agregando el hijo izquierdo a la cola junto con la distancia horizontal como hd-1 y el hijo derecho como hd+1.
- Use un mapa para almacenar el valor hd (como clave) y el último Node (como par) que tenga el valor hd correspondiente.
- Cada vez que encontramos una nueva distancia horizontal o una distancia horizontal existente, coloque los datos del Node para la distancia horizontal como clave. Por primera vez se agregará al mapa, la próxima vez reemplazará el valor. Esto asegurará que el elemento más abajo para esa distancia horizontal esté presente en el mapa.
- Finalmente, recorra el mapa y calcule la suma de todos los elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of binary tree
struct Node {
Node* left;
Node* right;
int hd;
int data;
};
// Function to create a new node
Node* newNode(int key)
{
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
// Function that returns the sum of
// nodes in bottom view of binary tree
int SumOfBottomView(Node* root)
{
if (root == NULL)
return 0;
queue<Node*> q;
map<int, int> m;
int hd = 0;
root->hd = hd;
int sum = 0;
// Push node and horizontal distance to queue
q.push(root);
while (q.size()) {
Node* temp = q.front();
q.pop();
hd = temp->hd;
// Put the dequeued tree node to Map
// having key as horizontal distance. Every
// time we find a node having same horizontal
// distance we need to replace the data in
// the map.
m[hd] = temp->data;
if (temp->left) {
temp->left->hd = hd - 1;
q.push(temp->left);
}
if (temp->right) {
temp->right->hd = hd + 1;
q.push(temp->right);
}
}
map<int, int>::iterator itr;
// Sum up all the nodes in bottom view of the tree
for (itr = m.begin(); itr != m.end(); itr++)
sum += itr->second;
return sum;
}
// Driver Code
int main()
{
Node* root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(5);
root->left->right = newNode(3);
root->right->left = newNode(4);
root->right->right = newNode(25);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
cout << SumOfBottomView(root);
return 0;
}
Java
// Java implementation of
// the above approach
import java.util.*;
class GFG{
// Structure of binary tree
public static class Node
{
public Node left;
public Node right;
public int hd;
public int data;
};
// Function to create
// a new node
static Node newNode(int key)
{
Node node = new Node();
node.data = key;
node.left = null;
node.right = null;
return node;
}
// Function that returns the sum of
// nodes in bottom view of binary tree
static int SumOfBottomView(Node root)
{
if (root == null)
return 0;
Queue<Node> q = new LinkedList<>();
HashMap<Integer,
Integer> m = new HashMap<Integer,
Integer>();
int hd = 0;
root.hd = hd;
int sum = 0;
// Push node and horizontal
// distance to queue
q.add(root);
while (q.size() != 0)
{
Node temp = q.poll();
hd = temp.hd;
// Put the dequeued tree node
// to Map having key as horizontal
// distance. Every time we find a
// node having same horizontal distance
// we need to replace the data in
// the map.
m.put(hd, temp.data);
if (temp.left != null)
{
temp.left.hd = hd - 1;
q.add(temp.left);
}
if (temp.right != null)
{
temp.right.hd = hd + 1;
q.add(temp.right);
}
}
// Sum up all the nodes in
// bottom view of the tree
for(int value : m.values())
{
sum += value;
}
return sum;
}
// Driver code
public static void main(String[] args)
{
Node root = newNode(20);
root.left = newNode(8);
root.right = newNode(22);
root.left.left = newNode(5);
root.left.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(25);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
System.out.println(SumOfBottomView(root));
}
}
// This code is contributed by pratham76
Python3
# Python3 implementation of the above approach
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.hd = None
# Function that returns the Sum of
# nodes in bottom view of binary tree
def SumOfBottomView(root):
if root == None:
return 0
q = []
m = {}
hd, Sum = 0, 0
root.hd = hd
# Push node and horizontal
# distance to queue
q.append(root)
while len(q) > 0:
temp = q.pop(0)
hd = temp.hd
# Put the dequeued tree node to Map
# having key as horizontal distance.
# Every time we find a node having
# same horizontal distance we need
# to replace the data in the map.
m[hd] = temp.data
if temp.left != None:
temp.left.hd = hd - 1
q.append(temp.left)
if temp.right != None:
temp.right.hd = hd + 1
q.append(temp.right)
# Sum up all the nodes in bottom
# view of the tree
for itr in m:
Sum += m[itr]
return Sum
# Driver Code
if __name__ == "__main__":
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.right.left = Node(4)
root.right.right = Node(25)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
print(SumOfBottomView(root))
# This code is contributed by Rituraj Jain
C#
// C# implementation of
// the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Structure of binary tree
public class Node
{
public Node left;
public Node right;
public int hd;
public int data;
};
// Function to create
// a new node
static Node newNode(int key)
{
Node node = new Node();
node.data = key;
node.left = null;
node.right = null;
return node;
}
// Function that returns the sum of
// nodes in bottom view of binary tree
static int SumOfBottomView(Node root)
{
if (root == null)
return 0;
Queue q = new Queue();
Dictionary<int,
int> m = new Dictionary<int,
int>();
int hd = 0;
root.hd = hd;
int sum = 0;
// Push node and horizontal
// distance to queue
q.Enqueue(root);
while (q.Count != 0)
{
Node temp = (Node)q.Peek();
q.Dequeue();
hd = temp.hd;
// Put the dequeued tree node
// to Map having key as horizontal
// distance. Every time we find a
// node having same horizontal distance
// we need to replace the data in
// the map.
m[hd] = temp.data;
if (temp.left != null)
{
temp.left.hd = hd - 1;
q.Enqueue(temp.left);
}
if (temp.right != null)
{
temp.right.hd = hd + 1;
q.Enqueue(temp.right);
}
}
// Sum up all the nodes in
// bottom view of the tree
foreach(KeyValuePair<int,
int> itr in m)
{
sum += itr.Value;
}
return sum;
}
// Driver code
public static void Main(string[] args)
{
Node root = newNode(20);
root.left = newNode(8);
root.right = newNode(22);
root.left.left = newNode(5);
root.left.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(25);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
Console.Write(SumOfBottomView(root));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript implementation of the approach
// Structure of binary tree
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.data = key;
this.hd;
}
}
// Function to create
// a new node
function newNode(key)
{
let node = new Node(key);
return node;
}
// Function that returns the sum of
// nodes in bottom view of binary tree
function SumOfBottomView(root)
{
if (root == null)
return 0;
let q = [];
let m = new Map();
let hd = 0;
root.hd = hd;
let sum = 0;
// Push node and horizontal
// distance to queue
q.push(root);
while (q.length != 0)
{
let temp = q[0];
q.shift();
hd = temp.hd;
// Put the dequeued tree node
// to Map having key as horizontal
// distance. Every time we find a
// node having same horizontal distance
// we need to replace the data in
// the map.
m.set(hd, temp.data);
if (temp.left != null)
{
temp.left.hd = hd - 1;
q.push(temp.left);
}
if (temp.right != null)
{
temp.right.hd = hd + 1;
q.push(temp.right);
}
}
// Sum up all the nodes in
// bottom view of the tree
m.forEach((value,key)=>{
sum += value;
})
return sum;
}
let root = newNode(20);
root.left = newNode(8);
root.right = newNode(22);
root.left.left = newNode(5);
root.left.right = newNode(3);
root.right.left = newNode(4);
root.right.right = newNode(25);
root.left.right.left = newNode(10);
root.left.right.right = newNode(14);
document.write(SumOfBottomView(root));
</script>
Producción:
58
Complejidad de tiempo : O(N * logN), donde N es el número total de Nodes en el árbol binario.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA