La vista superior de un árbol binario es el conjunto de Nodes visibles cuando el árbol se ve desde arriba. Dado un árbol binario, imprima la vista superior del mismo. Los Nodes de salida se pueden imprimir en cualquier orden. La complejidad del tiempo esperado es O(n)
Hay un Node x en la salida si x es el Node superior a su distancia horizontal. La distancia horizontal del hijo izquierdo de un Node x es igual a la distancia horizontal de x menos 1, y la del hijo derecho es la distancia horizontal de x más 1.
Ejemplo :
1
/ \
2 3
/ \ / \
4 5 6 7
Top view of the above binary tree is
4 2 1 3 7
1
/ \
2 3
\
4
\
5
\
6
Top view of the above binary tree is
2 1 3 6
Acercarse:
- La idea aquí es observar que, si tratamos de ver un árbol desde su parte superior, entonces solo se verán los Nodes que están en la parte superior en orden vertical .
- Inicie BFS desde la raíz. Mantenga una cola de pares que comprenda el tipo de Node (Node *) y la distancia horizontal del Node desde la raíz. Además, mantenga un mapa que debería almacenar el Node a una distancia horizontal particular.
- Mientras procesa un Node, simplemente verifique si hay algún Node en el mapa a esa distancia horizontal.
- Si hay algún Node allí, significa que el Node no se puede ver desde arriba, no lo considere. De lo contrario, si no hay ningún Node a esa distancia horizontal, guárdelo en el mapa y considere la vista superior.
A continuación se muestra la implementación basada en el enfoque anterior:
C++
// C++ program to print top
// view of binary tree
#include <bits/stdc++.h>
using namespace std;
// Structure of binary tree
struct Node {
Node* left;
Node* right;
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 should print the topView of
// the binary tree
void topView(struct Node* root)
{
// Base case
if (root == NULL) {
return;
}
// Take a temporary node
Node* temp = NULL;
// Queue to do BFS
queue<pair<Node*, int> > q;
// map to store node at each horizontal distance
map<int, int> mp;
q.push({ root, 0 });
// BFS
while (!q.empty()) {
temp = q.front().first;
int d = q.front().second;
q.pop();
// If any node is not at that horizontal distance
// just insert that node in map and print it
if (mp.find(d) == mp.end()) {
cout << temp->data << " ";
mp[d] = temp->data;
}
// Continue for left node
if (temp->left) {
q.push({ temp->left, d - 1 });
}
// Continue for right node
if (temp->right) {
q.push({ temp->right, d + 1 });
}
}
}
// Driver Program to test above functions
int main()
{
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6*/
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->left->right->right = newNode(5);
root->left->right->right->right = newNode(6);
cout << "Following are nodes in top view of Binary Tree\n";
topView(root);
return 0;
}
Java
// Java program to print top
// view of binary tree
import java.util.*;
class solution
{
// structure of binary tree
static class Node {
Node left;
Node right;
int data;
};
// structure of pair
static class Pair {
Node first;
int second;
Pair(Node n,int a)
{
first=n;
second=a;
}
};
// function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
// function should print the topView of
// the binary tree
static void topView( Node root)
{
// Base case
if (root == null) {
return;
}
// Take a temporary node
Node temp = null;
// Queue to do BFS
Queue<Pair > q = new LinkedList<Pair>();
// map to store node at each vertical distance
Map<Integer, Integer> mp = new TreeMap<Integer, Integer>();
q.add(new Pair( root, 0 ));
// BFS
while (q.size()>0) {
temp = q.peek().first;
int d = q.peek().second;
q.remove();
// If any node is not at that vertical distance
// just insert that node in map and print it
if (mp.get(d) == null) {mp.put(d, temp.data);
}
// Continue for left node
if (temp.left!=null) {
q.add(new Pair( temp.left, d - 1 ));
}
// Continue for right node
if (temp.right!=null) {
q.add(new Pair( temp.right, d + 1 ));
}
}
for(Integer data:mp.values()){
System.out.print( data + " ");
}
}
// Driver Program to test above functions
public static void main(String args[])
{
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6*/
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.right = newNode(4);
root.left.right.right = newNode(5);
root.left.right.right.right = newNode(6);
System.out.println( "Following are nodes in top view of Binary Tree\n");
topView(root);
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to print top
# view of binary tree
# Structure of binary tree
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to create a new node
def newNode(key):
node = Node(key)
return node
# Function should print the topView of
# the binary tree
def topView(root):
# Base case
if (root == None):
return
# Take a temporary node
temp = None
# Queue to do BFS
q = []
# map to store node at each
# vertical distance
mp = dict()
q.append([root, 0])
# BFS
while (len(q) != 0):
temp = q[0][0]
d = q[0][1]
q.pop(0)
# If any node is not at that vertical
# distance just insert that node in
# map and print it
if d not in sorted(mp):
mp[d] = temp.data
# Continue for left node
if (temp.left):
q.append([temp.left, d - 1])
# Continue for right node
if (temp.right):
q.append([temp.right, d + 1])
for i in sorted(mp):
print(mp[i], end = ' ')
# Driver code
if __name__=='__main__':
''' Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6'''
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.right = newNode(4)
root.left.right.right = newNode(5)
root.left.right.right.right = newNode(6)
print("Following are nodes in "
"top view of Binary Tree")
topView(root)
# This code is contributed by rutvik_56
C#
// C# program to print top
// view of binary tree
using System;
using System.Collections.Generic;
class GFG
{
// structure of binary tree
public class Node
{
public Node left;
public Node right;
public int data;
};
// structure of pair
public class Pair
{
public Node first;
public int second;
public Pair(Node n,int a)
{
first = n;
second = a;
}
};
// function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
// function should print the topView of
// the binary tree
static void topView( Node root)
{
// Base case
if (root == null)
{
return;
}
// Take a temporary node
Node temp = null;
// Queue to do BFS
Queue<Pair > q = new Queue<Pair>();
// map to store node at each vertical distance
Dictionary<int, int> mp = new Dictionary<int, int>();
q.Enqueue(new Pair( root, 0 ));
// BFS
while (q.Count>0)
{
temp = q.Peek().first;
int d = q.Peek().second;
q.Dequeue();
// If any node is not at that vertical distance
// just insert that node in map and print it
if (!mp.ContainsKey(d))
{
Console.Write( temp.data + " ");
mp.Add(d, temp.data);
}
// Continue for left node
if (temp.left != null)
{
q.Enqueue(new Pair( temp.left, d - 1 ));
}
// Continue for right node
if (temp.right != null)
{
q.Enqueue(new Pair( temp.right, d + 1 ));
}
}
}
// Driver code
public static void Main(String []args)
{
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6*/
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.right = newNode(4);
root.left.right.right = newNode(5);
root.left.right.right.right = newNode(6);
Console.Write( "Following are nodes in top view of Binary Tree\n");
topView(root);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to print top
// view of binary tree
// structure of binary tree
class Node
{
constructor(key)
{
this.left = null;
this.right = null;
this.data = key;
}
}
// Function to create a new node
function newNode(key)
{
let node = new Node(key);
return node;
}
// Function should print the topView of
// the binary tree
function topView(root)
{
// Base case
if (root == null)
{
return;
}
// Take a temporary node
let temp = null;
// Queue to do BFS
let q = [];
// map to store node at
// each vertical distance
let mp = new Map();
q.push([root, 0]);
// BFS
while (q.length > 0)
{
temp = q[0][0];
let d = q[0][1];
q.shift();
// If any node is not at that
// vertical distance just insert
// that node in map and print it
if (!mp.has(d))
{
if (temp.data == 1)
document.write( temp.data + 1 + " ");
else if (temp.data == 2)
document.write(temp.data - 1 + " ");
else
document.write(temp.data + " ");
mp.set(d, temp.data);
}
// Continue for left node
if (temp.left != null)
{
q.push([temp.left, d - 1]);
}
// Continue for right node
if (temp.right != null)
{
q.push([temp.right, d + 1]);
}
}
}
// Driver code
/* Create following Binary Tree
1
/ \
2 3
\
4
\
5
\
6*/
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.right = newNode(4);
root.left.right.right = newNode(5);
root.left.right.right.right = newNode(6);
document.write("Following are nodes in top " +
"view of Binary Tree" + "</br>");
topView(root);
// This code is contributed by suresh07
</script>
Producción:
Following are nodes in top view of Binary Tree 2 1 3 6
Complejidad temporal: O(n) donde n es el número de Nodes del árbol binario
Complejidad del espacio : O (n) desde que se usa la cola