Tree : Top View - HackerRank解题记录

题目：
You are given a pointer to the root of a binary tree. Print the top view of the binary tree.
Top view means when you look the tree from the top the nodes, what you will see will be called the top view of the tree. See the example below.
You only have to complete the function.
For example :

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4
Top View : 1 -> 2 -> 5 -> 6

Input Format

You are given a function,

void topView(node * root) {

}
Constraints

1 Nodes in the tree  500

Output Format

Print the values on a single line separated by space.

Sample Input

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4
Sample Output

1 2 5 6

Explanation

   1
    \
     2
      \
       5
      /  \
     3    6
      \
       4
From the top only nodes 1,2,5,6 will be visible.
思路：
先看一张图（图片来自搜）

TopView的意思是从上往下看，能看到的节点，并且是从左到右的顺序来输出。
我们可以给每个节点标上一个列的标识，设定root的列标识为0，右节点加1，左节点减1，然后再从层次遍历，把遇到的节点存到一个有序的map里面，列标识作为key，只要曾经有过这个key，那么就忽略，最终输出这个map里的内容即可
代码：

public static void topView(Node root) { Map<Integer,Integer> map = new TreeMap<Integer,Integer>(); Queue<Node> queue = new LinkedList<>(); Queue<Integer> queue2 = new LinkedList<Integer>(); queue.add(root); queue2.add(0); while (queue.peek() != null) { Node tmp = queue.poll(); Integer level = queue2.poll(); if (!map.containsKey(level)) { map.put(level, tmp.data); } if (tmp.left != null) { queue.offer(tmp.left); queue2.offer(level - 1); } if (tmp.right != null) { queue.offer(tmp.right); queue2.offer(level + 1); } } for (Map.Entry<Integer,Integer> entry : map.entrySet()) { System.out.print(entry.getValue()); System.out.print(" "); } }

原题链接：https://www.hackerrank.com/challenges/tree-top-view/problem