问题陈述
您将获得指向二叉树根的指针。打印二叉树的顶视图。您只需要完成该功能。
我的代码：
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语句，但我只需要执行其中一个。我尝试过切换但是它给出了常量表达式错误。我已经为这个问题找到了不同的解决方案。
所以我只想知道如果一次执行我们是否只能制作一个，即有没有办法修改我的代码而不改变方法？
使用以下方法可以很容易地解决此问题：
堆栈：打印根和左子树。
队列：打印正确的子树。
你的功能应该是这样的：
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()+" ");
}
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 ++中二叉树顶视图的代码。
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;
}
}
}
}
void topview_aux（node * root）
{
queue<node*> Q;
topview(root,Q);
}
一个@Karthik提到的一个非常类似的方法，但保持顺序，是将打印推迟到最后并保持顶视图节点在双端队列中排序。
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中定义 - GeeksforGeeks
你的方法不会起作用，因为当你打电话给left或right子树时，你会坚持下去。这种方法的问题在于您只是首先调用树的哪一侧。
也许你可以通过使用堆栈和队列来解决它，就像别人说的那样，但我觉得以下是一种更简单，更直观的方法：
（最后看到代码，非常简单）
解决这个问题的方法是从root维护horizontal distance，然后为每个不同的horizontal distance打印第一个节点。
什么是水平距离？
我只是拍摄你添加的图像。
特定Horizontal distance的node被定义为从根水平的数量。如果您看到任何边缘将成为垂直距离。
为了使根在左侧的所有节点更容易，以-ve水平距离和右侧正距离开始。
你如何计算水平距离？
如果你是正确的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 = 0
节点3,4,6,8有相同的水平距离0是什么意思？
这意味着当你从顶部看到所有这些节点在它上面垂直一行时。
如果它们垂直排成一行你看到了哪一个？
可以从root首先到达的那个。
你怎么找到第一个可以到达的？
像往常一样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;
}
}
这个实际上有效。不需要队列，但使用堆栈从左侧回溯，因为我们没有引用父级。
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实现已附加。如果递归求解，树的左侧更有趣，但是反转字符串（我的方式下面）更容易，只需要使用一种方法。
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);
}`
一个非常简单的递归解决方案，负责处理子节点的长分支。这是使用水平距离概念解决的。
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);
}
在java recursivish解决方案中。从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);
}
}