尝试使用两个 if 语句打印树的顶视图
Trying to print top view of a tree using two if statements
问题陈述
你得到了一个指向二叉树根的指针。打印二叉树的顶视图。
你只需要完成这个功能。
我的代码：
void top_view(Node root)
{
Node r = root;
if(r.left!=null){
top_view(r.left);
System.out.print(r.data + " ");
}
if(r.right!=null){
System.out.print(r.data + " ");
top_view(r.right);
}
}
每次调用函数时都会执行这两个if语句，但我只需要其中一个就可以执行。我试过 switch 但它给出了常量表达式错误。我已经为这个问题找到了不同的解决方案。
所以我只想知道如果一次执行我们是否可以只做一个，即有没有办法在不改变方法的情况下修复我的代码？
问题 link: https://www.hackerrank.com/challenges/tree-top-view
使用以下方法可以很容易地解决这个问题：
堆栈: 打印根和左子树。
Queue: 打印右子树。
你的函数应该是这样的：
void topview(Node root)
{
if(root==null)
return;
Stack<Integer> s=new Stack<Integer>();
s.push(root.data);
Node root2=root;
while(root.left!=null)
{
s.push(root.left.data);
root=root.left;
}
while(s.size()!=0)
System.out.print(s.pop()+" ");
Queue<Integer> q=new LinkedList<Integer>();
q.add(root2.right.data);
root2=root2.right;
while(root2.right!=null)
{
q.add(root2.right.data);
root2=root2.right;
}
while(q.size()!=0)
System.out.print(q.poll()+" ");
}
您的方法不会奏效，因为当您调用 left 或 right 子树时，您会坚持使用它。这种方法的问题是你只是被首先调用树的哪一侧驱动。
也许你可以像其他人说的那样使用堆栈和队列来解决它，但我觉得以下是一种更简单、更直观的方法：
（查看最后的代码，非常简单）
解决这个问题的方法是从根维护 horizontal distance，然后为每个不同的 horizontal distance.
打印第一个节点
什么是水平距离？
我正在拍你添加的图片。
特定 node 的 Horizontal distance 定义为从根 水平 的数量。如果您看到 no.of 条边，那将变成垂直距离。
为了使根左侧的所有节点更容易从负水平距离和右侧正距离开始。
水平距离如何计算？
如果您向右走 add 1，如果您向左走，请添加 -1。
所以
horizontal distance of 3 = 0
horizontal distance of 5 = -1
horizontal distance of 1 = -2
horizontal distance of 9 = -1
horizontal distance of 4 = 0
horizontal distance of 2 = 1
horizontal distance of 6 = 0
horizontal distance of 7 = 2
horizontal distance of 8 = 1
节点3,4,6水平距离相同0是什么意思？
这意味着当您从顶部看时，所有这些节点都在一条垂直线上。
如果它们垂直排成一行，你会看到哪一个？
第一个可以从根到达。
如何判断哪一个可以先到达？
像往常一样BFS
如何为您的示例打印解决方案？
有五个不同的水平距离值{-1,-2,0,1,2}
hor dist Nodes
0 - {3,6,8} // 3 comes first in BFS so print 3
-1 - {5,9} // 5 comes first in BFS so print 5
-2 - {1} // just print 1
1 - {2} // just print 2
2 - {7} // just print 7
所以它会打印 {3,5,1,2,7}
HashSet<Integer> set = new HashSet<>();
Queue<QueueItem> queue = new LinkedList<>();
queue.add(new QueueItem(root, 0)); // Horizontal distance of root is 0
while (!queue.isEmpty())
{
QueueItem temp = queue.poll();
int hd = temp.hd;
TreeNode n = temp.node;
// If this is the first node at its horizontal distance,
// then this node is in top view
if (!set.contains(hd))
{
set.add(hd);
System.out.print(n.key + " ");
}
if (n.left != null)
queue.add(new QueueItem(n.left, hd-1));
if (n.right != null)
queue.add(new QueueItem(n.right, hd+1));
}
如果您通过递归打印左侧，使用简单的 while 循环打印右侧，则解决方案非常简单。
void for_left(node *root)
{
if(!root->left)
{
cout<<root->data<<" ";
return;
}
for_left(root->left);
cout<<root->data<<" ";
return;
}
void top_view(node * root)
{
for_left(root->left);
cout<<root->data<<" ";
while(root->right)
{
cout<<(root->right)->data<<" ";
root=root->right;
}
}
附上我的Java实现。如果递归求解，树的左侧更有趣，但反转字符串（我在下面的方法）更容易，只需要使用一种方法。
public void top_view(Node root){
String output = "";
Node left = root.left;
Node right = root.right;
String leftOutput = "";
while(left != null){
leftOutput += left.data + " ";
left = left.left;
}
String left = "";
for(int i = leftOutput.length - 1; i >= 0; i--){
left += leftOutput.substring(i, i+1);
}
output += left;
output += " " + root.data + " ";
while(right != null){
output += right.data + " ";
right = right.right;
}
output = output.substring(1, output.length());
System.out.println(output);
}
void top_view(Node root)
{
if(root.left!=null) top_view(root.left);
if(root.left!=null || root.right!=null)
System.out.print(root.data + " ");
if(root.right!=null) top_view(root.right);
}
C++ 中更简单的方法
`// printing top view of the tree
void left_array(node *p)
{
if(p==NULL)
return;
else
{
left_array(p->left);
cout<<p->data<<" ";
}
}
void right_array(node *p)
{
if(p==NULL)
return;
else
{
cout<<p->data<<" ";
right_array(p->right);
}
}
void top_view(node * root)
{ int i=0;
node *t1=root;
node *t2=root;
left_array(t2);
right_array(t1->right);
}`
A very simple recursive solution which takes care of long branches of the child node. This is solved using horizontal distance concept.
public void printTopView(BNode root) {
Map<Integer, Integer> data = new TreeMap<Integer, Integer>();
printTopViewRecursive(data, root, 0);
for(int key : data.keySet()) {
System.out.print(data.get(key) +" ");
}
}
private void printTopViewRecursive(Map<Integer, Integer> hDMap, BNode root, int hD) {
if(root == null)
return;
if(!hDMap.containsKey(hD)) {
hDMap.put(hD, root.data);
}
printTopViewRecursive(hDMap, root.left,hD - 1);
printTopViewRecursive(hDMap, root.right, hD + 1);
}
这个确实有效。不需要队列，但使用堆栈以便从左侧回溯，因为我们没有对父级的引用。
void top_view(Node root)
{
Stack<Node> p = new Stack<Node>();
Node current = root;
while (current != null)
{
p.push(current);
current = current.left;
}
while (p.peek() != root)
{
System.out.print(p.pop().data + " ");
}
current = root;
while (current != null)
{
System.out.print(current.data + " ");
current = current.right;
}
}
在java递归解决方案中。从 C++ 代码转换
void top_view(Node root)
{
left_array(root);
right_array(root.right);
}
void left_array(Node p)
{
if(p==null)
return;
else
{
left_array(p.left);
System.out.printf("%d ",p.data);
}
}
void right_array(Node p)
{
if(p==null)
return;
else
{
System.out.printf("%d ",p.data);
right_array(p.right);
}
}
void top_view(Node root)
{
Node left = root;
Node right = root;
print_left(root.left);
System.out.print(root.data + " ");
print_right(root.right) ;
}
void print_left(Node start)
{
if(start != null)
{
print_left(start.left);
System.out.print(start.data + " ");
}
}
void print_right(Node start)
{
if(start != null)
{
System.out.print(start.data + " ");
print_right(start.right);
}
}
一种简单的递归方法：
void top_view(Node root)
{
print_top_view(root.left, "left");
System.out.print(root.data + " ");
print_top_view(root.right, "right");
}
void print_top_view(Node root, String side) {
if(side.equals("left")) {
if(root.left != null) {
print_top_view(root.left, "left");
}
System.out.print(root.data + " ");
} else if(side.equals("right")) {
System.out.print(root.data + " ");
if(root.right != null) {
print_top_view(root.right, "right");
}
}
}
if(root){
if(root->left !=NULL || root->right !=NULL){
if(root->left)
top_view(root->left);
cout<<root->data<<" ";
if(root->right)
top_view(root->right);
}}
这是c++中二叉树top-view的代码..
void topview(node* root,queue &Q)
{
if(!root)
return;
map<int,int> TV;
Q.push(root);
TV[root->data]=0;
map<int,int>:: iterator it;
int min=INT_MAX,max=INT_MIN;
while(!Q.empty())
{
node* temp =Q.front();
Q.pop();
int l=0;
for(it=TV.begin();it!=TV.end();it++)
{
if(it->first==temp->data)
{
l=it->second;
break;
}
}
if(l<min)
{min=l;}
if(l>max)
max=l;
if(temp->left)
{
Q.push(temp->left);
TV[temp->left->data] = l-1;
}
if(temp->right)
{
Q.push(temp->right);
TV[temp->right->data] = l+1;
}
}
cout<<max<<min<<endl;
for(int i =min;i<=max;i++)
{
for(it=TV.begin();it!=TV.end();it++)
{
if(it->second==i)
{
cout<<it->first;
break;
}
}
}
}
无效topview_aux（节点*根）
{
queue<node*> Q;
topview(root,Q);
}
一种与提到的 @Karthik 非常相似但保持顺序的方法是将打印推迟到最后并保持顶部视图节点在双端队列中排序。
- 我们使用 BFS 保证订单
- 每一轮我们检查当前节点的水平距离是否大于前几轮达到的最大距离（左节点的负距离）。
- 在双端队列的左端添加了 -ve 距离（左位置）的新顶视图节点，而在右端添加了 +ve 距离的右节点。
Java
中的示例解决方案
import java.util.*;
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
enum Position {
ROOT,
RIGHT,
LEFT
}
class NodePositionDetails {
Node node;
// Node position in the tree
Position pos;
// horizontal distance from the root (-ve for left nodes)
int hd;
public NodePositionDetails(Node node, Position pos, int hd) {
this.node = node;
this.pos = pos;
this.hd = hd;
}
}
public class TreeTopView {
public void topView(Node root) {
// max horizontal distance reached in the right direction uptill the current round
int reachedRightHD = 0;
// max horizontal distance reached in the left direction uptill the current round
int reachedLeftHD = 0;
if (root == null)
return;
// queue for saving nodes for BFS
Queue < NodePositionDetails > nodes = new LinkedList < > ();
// Double ended queue to save the top view nodes in order
Deque < Integer > topViewElements = new ArrayDeque < Integer > ();
// adding root node to BFS queue
NodePositionDetails rootNode = new NodePositionDetails(root, Position.ROOT, 0);
nodes.add(rootNode);
while (!nodes.isEmpty()) {
NodePositionDetails node = nodes.remove();
// in the first round, Root node is added, later rounds left and right nodes handled in order depending on BFS. if the current horizontal distance is larger than the last largest horizontal distance (saved in reachedLeftHD and reachedRightHD)
if (node.pos.equals(Position.LEFT) && node.hd == reachedLeftHD - 1) {
topViewElements.addFirst(node.node.data);
reachedLeftHD -= 1;
} else if (node.pos.equals(Position.RIGHT) && node.hd == reachedRightHD + 1) {
topViewElements.addLast(node.node.data);
reachedRightHD += 1;
} else if (node.pos.equals(Position.ROOT)) { // reachedLeftHD == 0 && reachedRightHD ==0
topViewElements.addFirst(node.node.data);
}
// Normal BFS, adding left and right nodes to the queue
if (node.node.left != null) {
nodes.add(new NodePositionDetails(node.node.left, Position.LEFT, node.hd - 1));
}
if (node.node.right != null) {
nodes.add(new NodePositionDetails(node.node.right, Position.RIGHT, node.hd + 1));
}
}
// print top elements view
for (Integer x: topViewElements) {
System.out.print(x + " ");
}
}
}
并进行测试：
public static void main(String[] args) throws java.lang.Exception {
/**
Test Case 1 & 2
1
/ \
2 3
/ \
7 4
/ \
8 5
\
6
Test Case 3: add long left branch under 3 (branch : left to the 3 3-> 8 -> 9 -> 10 -> 11
**/
Node root = new Node(1); //hd = 0
// test Case 1 -- output: 2 1 3 6
root.left = new Node(2); // hd = -1
root.right = new Node(3); // hd = +1
root.left.right = new Node(4); // hd = 0
root.left.right.right = new Node(5); // hd = +1
root.left.right.right.right = new Node(6); // hd = +2
// test case 2 -- output: 8 7 2 1 3 6
root.left.left = new Node(7); // hd = -2
root.left.left.left = new Node(8); // hd = -3
// test case 3 -- output: 11 7 2 1 3 6
root.left.left.left = null;
root.right.left = new Node(8); //hd = 0
root.right.left.left = new Node(9); // hd = -1
root.right.left.left.left = new Node(10); // hd = -2
root.right.left.left.left.left = new Node(11); //hd = -3
new TreeTopView().topView(root);
}
最简单的递归解决方案
void top_view(Node root)
{
// For left side of the tree
top_view_left(root);
// For Right side of the tree
top_view_right(root.right);
}
void top_view_left(Node root){
if(root != null)
{
// Postorder
top_view_left(root.left);
System.out.print(root.data + " ");
}
}
void top_view_right(Node root){
if(root != null)
{
// Preorder
System.out.print(root.data + " ");
top_view_right(root.right);
}
}
可以在这里找到解决方案 - Git hub URL
请注意，无论 hackerrank 问题是关于平衡树的，如果树处于如下所示的不平衡状态
1
/ \
2 3
\
4
\
5
\
6
对于这些树，需要一些复杂的逻辑，这在 geeksforgeeks here 中定义 - GeeksforGeeks
这个：
import queue
class NodeWrap:
def __init__(self, node, hd):
self.node = node
#horizontal distance
self.hd = hd
def topView(root):
d = {}
q = queue.Queue()
q.put(NodeWrap(root, 0))
while not q.empty():
node_wrap = q.get()
node = node_wrap.node
current_hd = node_wrap.hd
if d.get(current_hd) is None:
d[current_hd] = node
print(node.info, end=" ")
if node.left is not None:
q.put(NodeWrap(node.left, current_hd - 1))
if node.right is not None:
q.put(NodeWrap(node.right, current_hd + 1))
必须是 Python 上的工作解决方案，但由于某些原因，它在 hackerrank.com 上的 7 个测试用例中失败了 6 个。有人可以解释一下为什么会这样吗？
那些只运行 "left" 和 "right" 函数的人不理解这个任务。
Python 解决方案
使用广度优先遍历求解
def topView(root):
q = deque()
#Adding root node to the deque along with its Horizontal Distance from root.
q.append([root,0])
#Dictionary to store the {Horizontal Distance: First Node that has this distance}
s = {}
#Breadth First Traversal - [To keep track of the first Node that is visited.]
while q:
temp = q.popleft()
#Horizontal Distance from Root
d = temp[1]
#Adding the Left Child to the Queue (if Exists)
if temp[0].left is not None:
q.append([temp[0].left, d-1])
#Adding the Right Child to the Queue (if Exists)
if temp[0].right is not None:
q.append([temp[0].right, d+1])
#Adding the Horizontal Distance and the First Node that has this distance to Dictionary.
if d not in s:
s[d] = temp[0].info
#Printing out the Top View of Tree based on the values in the Dictionary - From least to Highest Horizontal Distance from Root Node.
for i in sorted(s):
print(s[i], end=" ")
def printTopView(root):
lst=[]
current1=root.left
while current1!=None:
lst.append(current1.key)
current1=current1.left
lst.reverse()
current2=root
while current2!=None:
lst.append(current2.key)
current2=current2.right
print(*lst)
上面的一些答案不起作用。我尝试对它们发表评论，但显然我没有正确的分数，因为我以前从未尝试在这里发表评论。
问题是需要对树做广度优先搜索，保证节点顺序正确。为了排除“模糊”的节点，另一个网站建议对每个节点进行排名。根为 0。节点左侧的所有分支的父秩为 -1。右边的所有分支都有父等级+1。排除与其祖先具有重复等级的任何节点。
然后按排名顺序打印出选中的节点。这适用于所有情况。
问题陈述
你得到了一个指向二叉树根的指针。打印二叉树的顶视图。 你只需要完成这个功能。
我的代码：
void top_view(Node root)
{
Node r = root;
if(r.left!=null){
top_view(r.left);
System.out.print(r.data + " ");
}
if(r.right!=null){
System.out.print(r.data + " ");
top_view(r.right);
}
}
每次调用函数时都会执行这两个if语句，但我只需要其中一个就可以执行。我试过 switch 但它给出了常量表达式错误。我已经为这个问题找到了不同的解决方案。
所以我只想知道如果一次执行我们是否可以只做一个，即有没有办法在不改变方法的情况下修复我的代码？
问题 link: https://www.hackerrank.com/challenges/tree-top-view
使用以下方法可以很容易地解决这个问题：
堆栈: 打印根和左子树。
Queue: 打印右子树。
你的函数应该是这样的：
void topview(Node root)
{
if(root==null)
return;
Stack<Integer> s=new Stack<Integer>();
s.push(root.data);
Node root2=root;
while(root.left!=null)
{
s.push(root.left.data);
root=root.left;
}
while(s.size()!=0)
System.out.print(s.pop()+" ");
Queue<Integer> q=new LinkedList<Integer>();
q.add(root2.right.data);
root2=root2.right;
while(root2.right!=null)
{
q.add(root2.right.data);
root2=root2.right;
}
while(q.size()!=0)
System.out.print(q.poll()+" ");
}
您的方法不会奏效，因为当您调用 left 或 right 子树时，您会坚持使用它。这种方法的问题是你只是被首先调用树的哪一侧驱动。
也许你可以像其他人说的那样使用堆栈和队列来解决它，但我觉得以下是一种更简单、更直观的方法：
（查看最后的代码，非常简单）
解决这个问题的方法是从根维护 horizontal distance，然后为每个不同的 horizontal distance.
什么是水平距离？
我正在拍你添加的图片。
node 的 Horizontal distance 定义为从根 水平 的数量。如果您看到 no.of 条边，那将变成垂直距离。
为了使根左侧的所有节点更容易从负水平距离和右侧正距离开始。
水平距离如何计算？
如果您向右走 add 1，如果您向左走，请添加 -1。
所以
horizontal distance of 3 = 0
horizontal distance of 5 = -1
horizontal distance of 1 = -2
horizontal distance of 9 = -1
horizontal distance of 4 = 0
horizontal distance of 2 = 1
horizontal distance of 6 = 0
horizontal distance of 7 = 2
horizontal distance of 8 = 1
节点3,4,6水平距离相同0是什么意思？
这意味着当您从顶部看时，所有这些节点都在一条垂直线上。
如果它们垂直排成一行，你会看到哪一个？
第一个可以从根到达。
如何判断哪一个可以先到达？
像往常一样BFS
如何为您的示例打印解决方案？
有五个不同的水平距离值{-1,-2,0,1,2}
hor dist Nodes
0 - {3,6,8} // 3 comes first in BFS so print 3
-1 - {5,9} // 5 comes first in BFS so print 5
-2 - {1} // just print 1
1 - {2} // just print 2
2 - {7} // just print 7
所以它会打印 {3,5,1,2,7}
HashSet<Integer> set = new HashSet<>();
Queue<QueueItem> queue = new LinkedList<>();
queue.add(new QueueItem(root, 0)); // Horizontal distance of root is 0
while (!queue.isEmpty())
{
QueueItem temp = queue.poll();
int hd = temp.hd;
TreeNode n = temp.node;
// If this is the first node at its horizontal distance,
// then this node is in top view
if (!set.contains(hd))
{
set.add(hd);
System.out.print(n.key + " ");
}
if (n.left != null)
queue.add(new QueueItem(n.left, hd-1));
if (n.right != null)
queue.add(new QueueItem(n.right, hd+1));
}
如果您通过递归打印左侧，使用简单的 while 循环打印右侧，则解决方案非常简单。
void for_left(node *root)
{
if(!root->left)
{
cout<<root->data<<" ";
return;
}
for_left(root->left);
cout<<root->data<<" ";
return;
}
void top_view(node * root)
{
for_left(root->left);
cout<<root->data<<" ";
while(root->right)
{
cout<<(root->right)->data<<" ";
root=root->right;
}
}
附上我的Java实现。如果递归求解，树的左侧更有趣，但反转字符串（我在下面的方法）更容易，只需要使用一种方法。
public void top_view(Node root){
String output = "";
Node left = root.left;
Node right = root.right;
String leftOutput = "";
while(left != null){
leftOutput += left.data + " ";
left = left.left;
}
String left = "";
for(int i = leftOutput.length - 1; i >= 0; i--){
left += leftOutput.substring(i, i+1);
}
output += left;
output += " " + root.data + " ";
while(right != null){
output += right.data + " ";
right = right.right;
}
output = output.substring(1, output.length());
System.out.println(output);
}
void top_view(Node root)
{
if(root.left!=null) top_view(root.left);
if(root.left!=null || root.right!=null)
System.out.print(root.data + " ");
if(root.right!=null) top_view(root.right);
}
C++ 中更简单的方法
`// printing top view of the tree
void left_array(node *p)
{
if(p==NULL)
return;
else
{
left_array(p->left);
cout<<p->data<<" ";
}
}
void right_array(node *p)
{
if(p==NULL)
return;
else
{
cout<<p->data<<" ";
right_array(p->right);
}
}
void top_view(node * root)
{ int i=0;
node *t1=root;
node *t2=root;
left_array(t2);
right_array(t1->right);
}`
A very simple recursive solution which takes care of long branches of the child node. This is solved using horizontal distance concept.
public void printTopView(BNode root) {
Map<Integer, Integer> data = new TreeMap<Integer, Integer>();
printTopViewRecursive(data, root, 0);
for(int key : data.keySet()) {
System.out.print(data.get(key) +" ");
}
}
private void printTopViewRecursive(Map<Integer, Integer> hDMap, BNode root, int hD) {
if(root == null)
return;
if(!hDMap.containsKey(hD)) {
hDMap.put(hD, root.data);
}
printTopViewRecursive(hDMap, root.left,hD - 1);
printTopViewRecursive(hDMap, root.right, hD + 1);
}
这个确实有效。不需要队列，但使用堆栈以便从左侧回溯，因为我们没有对父级的引用。
void top_view(Node root)
{
Stack<Node> p = new Stack<Node>();
Node current = root;
while (current != null)
{
p.push(current);
current = current.left;
}
while (p.peek() != root)
{
System.out.print(p.pop().data + " ");
}
current = root;
while (current != null)
{
System.out.print(current.data + " ");
current = current.right;
}
}
在java递归解决方案中。从 C++ 代码转换
void top_view(Node root)
{
left_array(root);
right_array(root.right);
}
void left_array(Node p)
{
if(p==null)
return;
else
{
left_array(p.left);
System.out.printf("%d ",p.data);
}
}
void right_array(Node p)
{
if(p==null)
return;
else
{
System.out.printf("%d ",p.data);
right_array(p.right);
}
}
void top_view(Node root)
{
Node left = root;
Node right = root;
print_left(root.left);
System.out.print(root.data + " ");
print_right(root.right) ;
}
void print_left(Node start)
{
if(start != null)
{
print_left(start.left);
System.out.print(start.data + " ");
}
}
void print_right(Node start)
{
if(start != null)
{
System.out.print(start.data + " ");
print_right(start.right);
}
}
一种简单的递归方法：
void top_view(Node root)
{
print_top_view(root.left, "left");
System.out.print(root.data + " ");
print_top_view(root.right, "right");
}
void print_top_view(Node root, String side) {
if(side.equals("left")) {
if(root.left != null) {
print_top_view(root.left, "left");
}
System.out.print(root.data + " ");
} else if(side.equals("right")) {
System.out.print(root.data + " ");
if(root.right != null) {
print_top_view(root.right, "right");
}
}
}
if(root){
if(root->left !=NULL || root->right !=NULL){
if(root->left)
top_view(root->left);
cout<<root->data<<" ";
if(root->right)
top_view(root->right);
}}
这是c++中二叉树top-view的代码..
void topview(node* root,queue &Q)
{
if(!root)
return;
map<int,int> TV;
Q.push(root);
TV[root->data]=0;
map<int,int>:: iterator it;
int min=INT_MAX,max=INT_MIN;
while(!Q.empty())
{
node* temp =Q.front();
Q.pop();
int l=0;
for(it=TV.begin();it!=TV.end();it++)
{
if(it->first==temp->data)
{
l=it->second;
break;
}
}
if(l<min)
{min=l;}
if(l>max)
max=l;
if(temp->left)
{
Q.push(temp->left);
TV[temp->left->data] = l-1;
}
if(temp->right)
{
Q.push(temp->right);
TV[temp->right->data] = l+1;
}
}
cout<<max<<min<<endl;
for(int i =min;i<=max;i++)
{
for(it=TV.begin();it!=TV.end();it++)
{
if(it->second==i)
{
cout<<it->first;
break;
}
}
}
}
无效topview_aux（节点*根）
{
queue<node*> Q;
topview(root,Q);
}
一种与提到的 @Karthik 非常相似但保持顺序的方法是将打印推迟到最后并保持顶部视图节点在双端队列中排序。
- 我们使用 BFS 保证订单
- 每一轮我们检查当前节点的水平距离是否大于前几轮达到的最大距离（左节点的负距离）。
- 在双端队列的左端添加了 -ve 距离（左位置）的新顶视图节点，而在右端添加了 +ve 距离的右节点。
Java
中的示例解决方案import java.util.*;
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
enum Position {
ROOT,
RIGHT,
LEFT
}
class NodePositionDetails {
Node node;
// Node position in the tree
Position pos;
// horizontal distance from the root (-ve for left nodes)
int hd;
public NodePositionDetails(Node node, Position pos, int hd) {
this.node = node;
this.pos = pos;
this.hd = hd;
}
}
public class TreeTopView {
public void topView(Node root) {
// max horizontal distance reached in the right direction uptill the current round
int reachedRightHD = 0;
// max horizontal distance reached in the left direction uptill the current round
int reachedLeftHD = 0;
if (root == null)
return;
// queue for saving nodes for BFS
Queue < NodePositionDetails > nodes = new LinkedList < > ();
// Double ended queue to save the top view nodes in order
Deque < Integer > topViewElements = new ArrayDeque < Integer > ();
// adding root node to BFS queue
NodePositionDetails rootNode = new NodePositionDetails(root, Position.ROOT, 0);
nodes.add(rootNode);
while (!nodes.isEmpty()) {
NodePositionDetails node = nodes.remove();
// in the first round, Root node is added, later rounds left and right nodes handled in order depending on BFS. if the current horizontal distance is larger than the last largest horizontal distance (saved in reachedLeftHD and reachedRightHD)
if (node.pos.equals(Position.LEFT) && node.hd == reachedLeftHD - 1) {
topViewElements.addFirst(node.node.data);
reachedLeftHD -= 1;
} else if (node.pos.equals(Position.RIGHT) && node.hd == reachedRightHD + 1) {
topViewElements.addLast(node.node.data);
reachedRightHD += 1;
} else if (node.pos.equals(Position.ROOT)) { // reachedLeftHD == 0 && reachedRightHD ==0
topViewElements.addFirst(node.node.data);
}
// Normal BFS, adding left and right nodes to the queue
if (node.node.left != null) {
nodes.add(new NodePositionDetails(node.node.left, Position.LEFT, node.hd - 1));
}
if (node.node.right != null) {
nodes.add(new NodePositionDetails(node.node.right, Position.RIGHT, node.hd + 1));
}
}
// print top elements view
for (Integer x: topViewElements) {
System.out.print(x + " ");
}
}
}
并进行测试：
public static void main(String[] args) throws java.lang.Exception {
/**
Test Case 1 & 2
1
/ \
2 3
/ \
7 4
/ \
8 5
\
6
Test Case 3: add long left branch under 3 (branch : left to the 3 3-> 8 -> 9 -> 10 -> 11
**/
Node root = new Node(1); //hd = 0
// test Case 1 -- output: 2 1 3 6
root.left = new Node(2); // hd = -1
root.right = new Node(3); // hd = +1
root.left.right = new Node(4); // hd = 0
root.left.right.right = new Node(5); // hd = +1
root.left.right.right.right = new Node(6); // hd = +2
// test case 2 -- output: 8 7 2 1 3 6
root.left.left = new Node(7); // hd = -2
root.left.left.left = new Node(8); // hd = -3
// test case 3 -- output: 11 7 2 1 3 6
root.left.left.left = null;
root.right.left = new Node(8); //hd = 0
root.right.left.left = new Node(9); // hd = -1
root.right.left.left.left = new Node(10); // hd = -2
root.right.left.left.left.left = new Node(11); //hd = -3
new TreeTopView().topView(root);
}
最简单的递归解决方案
void top_view(Node root)
{
// For left side of the tree
top_view_left(root);
// For Right side of the tree
top_view_right(root.right);
}
void top_view_left(Node root){
if(root != null)
{
// Postorder
top_view_left(root.left);
System.out.print(root.data + " ");
}
}
void top_view_right(Node root){
if(root != null)
{
// Preorder
System.out.print(root.data + " ");
top_view_right(root.right);
}
}
可以在这里找到解决方案 - Git hub URL
请注意，无论 hackerrank 问题是关于平衡树的，如果树处于如下所示的不平衡状态
1
/ \
2 3
\
4
\
5
\
6
对于这些树，需要一些复杂的逻辑，这在 geeksforgeeks here 中定义 - GeeksforGeeks
这个：
import queue
class NodeWrap:
def __init__(self, node, hd):
self.node = node
#horizontal distance
self.hd = hd
def topView(root):
d = {}
q = queue.Queue()
q.put(NodeWrap(root, 0))
while not q.empty():
node_wrap = q.get()
node = node_wrap.node
current_hd = node_wrap.hd
if d.get(current_hd) is None:
d[current_hd] = node
print(node.info, end=" ")
if node.left is not None:
q.put(NodeWrap(node.left, current_hd - 1))
if node.right is not None:
q.put(NodeWrap(node.right, current_hd + 1))
必须是 Python 上的工作解决方案，但由于某些原因，它在 hackerrank.com 上的 7 个测试用例中失败了 6 个。有人可以解释一下为什么会这样吗？
那些只运行 "left" 和 "right" 函数的人不理解这个任务。
Python 解决方案
使用广度优先遍历求解
def topView(root):
q = deque()
#Adding root node to the deque along with its Horizontal Distance from root.
q.append([root,0])
#Dictionary to store the {Horizontal Distance: First Node that has this distance}
s = {}
#Breadth First Traversal - [To keep track of the first Node that is visited.]
while q:
temp = q.popleft()
#Horizontal Distance from Root
d = temp[1]
#Adding the Left Child to the Queue (if Exists)
if temp[0].left is not None:
q.append([temp[0].left, d-1])
#Adding the Right Child to the Queue (if Exists)
if temp[0].right is not None:
q.append([temp[0].right, d+1])
#Adding the Horizontal Distance and the First Node that has this distance to Dictionary.
if d not in s:
s[d] = temp[0].info
#Printing out the Top View of Tree based on the values in the Dictionary - From least to Highest Horizontal Distance from Root Node.
for i in sorted(s):
print(s[i], end=" ")
def printTopView(root):
lst=[]
current1=root.left
while current1!=None:
lst.append(current1.key)
current1=current1.left
lst.reverse()
current2=root
while current2!=None:
lst.append(current2.key)
current2=current2.right
print(*lst)
上面的一些答案不起作用。我尝试对它们发表评论，但显然我没有正确的分数，因为我以前从未尝试在这里发表评论。
问题是需要对树做广度优先搜索，保证节点顺序正确。为了排除“模糊”的节点，另一个网站建议对每个节点进行排名。根为 0。节点左侧的所有分支的父秩为 -1。右边的所有分支都有父等级+1。排除与其祖先具有重复等级的任何节点。
然后按排名顺序打印出选中的节点。这适用于所有情况。