原文:
二叉树的俯视图是从顶部看树时可见的一组节点。给定一棵二叉树，打印它的顶视图。输出节点可以以任何顺序打印。预期时间复杂度为 0(n)
如果 x 是水平距离上最顶端的节点，则输出中有一个节点 x。节点 x 的左子节点的水平距离等于 x 减 1 的水平距离，右子节点的水平距离等于 x 加 1 的水平距离。
示例:
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
进场:
- 这里的想法是观察，如果我们试图从一棵树的顶部看到它，那么只有垂直顺序在顶部的节点才会被看到。
- 从根开始 bfs 。维护由节点(节点)* 类型和节点到根的垂直距离组成的队列对。此外，维护一个地图，该地图应在特定的垂直距离存储节点。
- 在处理一个节点时，只需检查地图中该垂直距离处是否有任何节点。
- 如果有任何一个节点在那里，说明从上面看不到这个节点，不要考虑。否则，如果在垂直距离上没有节点，将它存储在地图中并考虑俯视图。
以下是基于上述方法的实现:
c
// c program to print top
// view of binary tree
#include
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 > q;
// map to store node at each vertical distance
map 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 vertical 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 q = new linkedlist();
// map to store node at each vertical distance
map mp = new treemap();
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
python 3
# 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 q = new queue();
// map to store node at each vertical distance
dictionary mp = new dictionary();
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 */
java 描述语言
output:
following are nodes in top view of binary tree
2 1 3 6
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
