Dado un árbol binario, encuentre la suma vertical de los Nodes que están en la misma línea vertical. Imprime todas las sumas a través de diferentes líneas verticales.
Ejemplos:
1
/ \
2 3
/ \ / \
4 5 6 7
El árbol tiene 5 líneas verticales.
- Vertical-Line-1 tiene solo un Node 4 => la suma vertical es 4
- Vertical-Line-2: tiene solo un Node 2 => la suma vertical es 2
- Vertical-Line-3: tiene tres Nodes: 1,5,6 => la suma vertical es 1+5+6 = 12
- Vertical-Line-4: tiene un solo Node 3 => la suma vertical es 3
- Vertical-Line-5: tiene un solo Node 7 => la suma vertical es 7
- Entonces, la salida esperada es 4, 2, 12, 3 y 7
Necesitamos verificar las distancias horizontales desde la raíz para todos los Nodes. Si dos Nodes tienen la misma Distancia Horizontal (HD), entonces están en la misma línea vertical. La idea de HD es simple. HD para raíz es 0, un borde derecho (borde que se conecta al subárbol derecho) se considera como una distancia horizontal de +1 y un borde izquierdo se considera como una distancia horizontal de -1. Por ejemplo, en el árbol anterior, HD para el Node 4 está en -2, HD para el Node 2 es -1, HD para 5 y 6 es 0 y HD para el Node 7 es +2.
Podemos hacer un recorrido en orden del árbol binario dado. Mientras recorremos el árbol, podemos calcular HD de forma recursiva. Inicialmente pasamos la distancia horizontal como 0 para la raíz. Para el subárbol izquierdo, pasamos la Distancia horizontal como Distancia horizontal de la raíz menos 1. Para el subárbol derecho, pasamos la Distancia horizontal como Distancia horizontal de la raíz más 1.
La siguiente es la implementación de Java para lo mismo. HashMap se utiliza para almacenar las sumas verticales para diferentes distancias horizontales. Gracias a Nages por sugerir este método.
C++
// C++ program to find Vertical Sum in
// a given Binary Tree
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *left, *right;
};
// A utility function to create a new
// Binary Tree node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Traverses the tree in in-order form and
// populates a hashMap that contains the
// vertical sum
void verticalSumUtil(Node *node, int hd,
map<int, int> &Map)
{
// Base case
if (node == NULL) return;
// Recur for left subtree
verticalSumUtil(node->left, hd-1, Map);
// Add val of current node to
// map entry of corresponding hd
Map[hd] += node->data;
// Recur for right subtree
verticalSumUtil(node->right, hd+1, Map);
}
// Function to find vertical sum
void verticalSum(Node *root)
{
// a map to store sum of nodes for each
// horizontal distance
map < int, int> Map;
map < int, int> :: iterator it;
// populate the map
verticalSumUtil(root, 0, Map);
// Prints the values stored by VerticalSumUtil()
for (it = Map.begin(); it != Map.end(); ++it)
{
cout << it->first << ": "
<< it->second << endl;
}
}
// Driver program to test above functions
int main()
{
// Create binary tree as shown in above figure
Node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->right = newNode(8);
root->right->right->right = newNode(9);
cout << "Following are the values of vertical"
" sums with the positions of the "
"columns with respect to root\n";
verticalSum(root);
return 0;
}
// This code is contributed by Aditi Sharma
Java
import java.util.TreeMap;
// Class for a tree node
class TreeNode {
// data members
private int key;
private TreeNode left;
private TreeNode right;
// Accessor methods
public int key() { return key; }
public TreeNode left() { return left; }
public TreeNode right() { return right; }
// Constructor
public TreeNode(int key)
{ this.key = key; left = null; right = null; }
// Methods to set left and right subtrees
public void setLeft(TreeNode left) { this.left = left; }
public void setRight(TreeNode right) { this.right = right; }
}
// Class for a Binary Tree
class Tree {
private TreeNode root;
// Constructors
public Tree() { root = null; }
public Tree(TreeNode n) { root = n; }
// Method to be called by the consumer classes
// like Main class
public void VerticalSumMain() { VerticalSum(root); }
// A wrapper over VerticalSumUtil()
private void VerticalSum(TreeNode root) {
// base case
if (root == null) { return; }
// Creates an empty TreeMap hM
TreeMap<Integer, Integer> hM =
new TreeMap<Integer, Integer>();
// Calls the VerticalSumUtil() to store the
// vertical sum values in hM
VerticalSumUtil(root, 0, hM);
// Prints the values stored by VerticalSumUtil()
if (hM != null) {
System.out.println(hM.entrySet());
}
}
// Traverses the tree in in-order form and builds
// a hashMap hM that contains the vertical sum
private void VerticalSumUtil(TreeNode root, int hD,
TreeMap<Integer, Integer> hM) {
// base case
if (root == null) { return; }
// Store the values in hM for left subtree
VerticalSumUtil(root.left(), hD - 1, hM);
// Update vertical sum for hD of this node
int prevSum = (hM.get(hD) == null) ? 0 : hM.get(hD);
hM.put(hD, prevSum + root.key());
// Store the values in hM for right subtree
VerticalSumUtil(root.right(), hD + 1, hM);
}
}
// Driver class to test the verticalSum methods
public class Main {
public static void main(String[] args) {
/* Create the following Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
*/
TreeNode root = new TreeNode(1);
root.setLeft(new TreeNode(2));
root.setRight(new TreeNode(3));
root.left().setLeft(new TreeNode(4));
root.left().setRight(new TreeNode(5));
root.right().setLeft(new TreeNode(6));
root.right().setRight(new TreeNode(7));
Tree t = new Tree(root);
System.out.println("Following are the values of" +
" vertical sums with the positions" +
" of the columns with respect to root ");
t.VerticalSumMain();
}
}
Python3
# Python3 program to find Vertical Sum in
# a given Binary Tree
# Node definition
class newNode:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Traverses the tree in in-order form and
# populates a hashMap that contains the
# vertical sum
def verticalSumUtil(root, hd, Map):
# Base case
if(root == None):
return
# Recur for left subtree
verticalSumUtil(root.left, hd - 1, Map)
# Add val of current node to
# map entry of corresponding hd
if(hd in Map.keys()):
Map[hd] = Map[hd] + root.data
else:
Map[hd] = root.data
# Recur for right subtree
verticalSumUtil(root.right, hd + 1, Map)
# Function to find vertical_sum
def verticalSum(root):
# a dictionary to store sum of
# nodes for each horizontal distance
Map = {}
# Populate the dictionary
verticalSumUtil(root, 0, Map);
# Prints the values stored
# by VerticalSumUtil()
for i,j in Map.items():
print(i, "=", j, end = ", ")
# Driver Code
if __name__ == "__main__":
''' Create the following Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
'''
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(5)
root.right.left = newNode(6)
root.right.right = newNode(7)
print("Following are the values of vertical "
"sums with the positions of the "
"columns with respect to root")
verticalSum(root)
# This code is contributed by vipinyadav15799
C#
// C# program to find Vertical Sum in
// a given Binary Tree
using System;
using System.Collections.Generic;
// Class for a tree node
class TreeNode
{
// data members
public int key;
public TreeNode left;
public TreeNode right;
// Accessor methods
public int Key()
{
return key;
}
public TreeNode Left() { return left; }
public TreeNode Right() { return right; }
// Constructor
public TreeNode(int key)
{
this.key = key;
left = null;
right = null;
}
// Methods to set left and right subtrees
public void setLeft(TreeNode left)
{
this.left = left;
}
public void setRight(TreeNode right)
{
this.right = right;
}
}
// Class for a Binary Tree
class Tree
{
private TreeNode root;
// Constructors
public Tree() { root = null; }
public Tree(TreeNode n) { root = n; }
// Method to be called by the consumer classes
// like Main class
public void VerticalSumMain()
{
VerticalSum(root);
}
// A wrapper over VerticalSumUtil()
private void VerticalSum(TreeNode root)
{
// base case
if (root == null) { return; }
// Creates an empty hashMap hM
Dictionary<int,
int> hM = new Dictionary<int,
int>();
// Calls the VerticalSumUtil() to store the
// vertical sum values in hM
VerticalSumUtil(root, 0, hM);
// Prints the values stored by VerticalSumUtil()
if (hM != null)
{
Console.Write("[");
foreach(KeyValuePair<int, int> entry in hM)
{
Console.Write(entry.Key + " = " +
entry.Value + ", ");
}
Console.Write("]");
}
}
// Traverses the tree in in-order form and builds
// a hashMap hM that contains the vertical sum
private void VerticalSumUtil(TreeNode root, int hD,
Dictionary<int, int> hM)
{
// base case
if (root == null) { return; }
// Store the values in hM for left subtree
VerticalSumUtil(root.Left(), hD - 1, hM);
// Update vertical sum for hD of this node
int prevSum = 0;
if(hM.ContainsKey(hD))
{
prevSum = hM[hD];
hM[hD] = prevSum + root.Key();
}
else
hM.Add(hD, prevSum + root.Key());
// Store the values in hM for right subtree
VerticalSumUtil(root.Right(), hD + 1, hM);
}
}
// Driver Code
public class GFG
{
public static void Main(String[] args)
{
/* Create the following Binary Tree
1
/ \
2 3
/ \ / \
4 5 6 7
*/
TreeNode root = new TreeNode(1);
root.setLeft(new TreeNode(2));
root.setRight(new TreeNode(3));
root.Left().setLeft(new TreeNode(4));
root.Left().setRight(new TreeNode(5));
root.Right().setLeft(new TreeNode(6));
root.Right().setRight(new TreeNode(7));
Tree t = new Tree(root);
Console.WriteLine("Following are the values of" +
" vertical sums with the positions" +
" of the columns with respect to root ");
t.VerticalSumMain();
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find Vertical Sum in
// a given Binary Tree
// Node definition
class newNode{
constructor(data){
this.left = null
this.right = null
this.data = data
}
}
// Traverses the tree in in-order form and
// populates a hashMap that contains the
// vertical sum
function verticalSumUtil(root, hd, map){
// Base case
if(root == null)
return;
// Recur for left subtree
verticalSumUtil(root.left, hd - 1, map)
// Add val of current node to
// map entry of corresponding hd
if(map.has(hd) == true)
map.set(hd , map.get(hd) + root.data)
else
map.set(hd , root.data)
// Recur for right subtree
verticalSumUtil(root.right, hd + 1, map)
}
// Function to find vertical_sum
function verticalSum(root){
// a dictionary to store sum of
// nodes for each horizontal distance
let map = new Map()
// Populate the dictionary
verticalSumUtil(root, 0, map);
// Prints the values stored
// by VerticalSumUtil()
for(const [i,j] of map.entries())
document.write(i + ": " + j)
}
// Driver Code
// Create the following Binary Tree
// 1
// / \
// 2 3
/// \ / \
// 4 5 6 7
root = new newNode(1)
root.left = new newNode(2)
root.right = new newNode(3)
root.left.left = new newNode(4)
root.left.right = new newNode(5)
root.right.left = new newNode(6)
root.right.right = new newNode(7)
root.right.left.right = new newNode(8);
root.right.right.right = new newNode(9);
document.write("Following are the values of vertical sums with the positions of the columns with respect to root")
verticalSum(root)
// This code is contributed by shinjanpatra
</script>
Producción
Following are the values of vertical sums with the positions of the columns with respect to root -2: 4 -1: 2 0: 12 1: 11 2: 7 3: 9
Suma vertical en árbol binario | Conjunto 2 (espacio optimizado)
Complejidad de tiempo: O (nlogn)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA