Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- class Node {
- Node left;
- Node right;
- int data;
- Node(int data) {
- this.data = data;
- left = null;
- right = null;
- }
- }
- class Solution {
- /*
- class Node
- int data;
- Node left;
- Node right;
- */
- public static void topView(Node root) {
- int shift = 0;
- int level = 0;
- LinkedHashMap<Node, Integer> nodeLevel = new LinkedHashMap<>();
- LinkedHashMap<Integer, Node> nodeShift = new LinkedHashMap<>();
- LinkedList<Node> lefts = new LinkedList<>();
- LinkedList<Integer> leftLevel = new LinkedList<>();
- LinkedList<Integer> leftShift = new LinkedList<>();
- Node current = root;
- Node other;
- while (true) {
- //System.out.println(current.data);
- if (current.left != null) {
- lefts.add(current.left);
- leftLevel.addLast(level + 1);
- leftShift.addLast(shift - 1);
- }
- if (!nodeShift.containsKey(shift)) {
- nodeShift.put(shift, current);
- nodeLevel.put(current, level);
- } else {
- other = nodeShift.get(shift);
- if (level < nodeLevel.get(other)) {
- nodeShift.put(shift, current);
- nodeLevel.remove(other);
- nodeLevel.put(current, level);
- }
- }
- if (current.right == null) {
- if (lefts.isEmpty()) {
- break;
- }
- current = lefts.getLast();
- level = leftLevel.getLast();
- shift = leftShift.getLast();
- lefts.removeLast();
- leftLevel.removeLast();
- leftShift.removeLast();
- continue;
- }
- current = current.right;
- level++;
- shift++;
- }
- List<Map.Entry<Integer, Node>> nodes = new ArrayList<>(nodeShift.entrySet());
- Collections.sort(nodes, new Comparator<Map.Entry<Integer, Node>>() {
- public int compare(Map.Entry<Integer, Node> a, Map.Entry<Integer, Node> b) {
- return a.getKey() - b.getKey();
- }
- });
- nodes.forEach(i -> System.out.print(i.getValue().data + " "));
- }
- public static Node insert(Node root, int data) {
- if(root == null) {
- return new Node(data);
- } else {
- Node cur;
- if(data <= root.data) {
- cur = insert(root.left, data);
- root.left = cur;
- } else {
- cur = insert(root.right, data);
- root.right = cur;
- }
- return root;
- }
- }
- public static void main(String[] args) {
- Scanner scan = new Scanner(System.in);
- int t = scan.nextInt();
- Node root = null;
- while(t-- > 0) {
- int data = scan.nextInt();
- root = insert(root, data);
- }
- scan.close();
- topView(root);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement