1
/**
2
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
3
 * right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left,
4
 * TreeNode right) { this.val = val; this.left = left; this.right = right; } }
5
 */
6
class Solution {
7

8
  private static class MNode {
9
    TreeNode Node;
10
    int hDist;
11
    int level;
12

13
    MNode(TreeNode node, int hd, int l) {
14
      Node = node;
15
      hDist = hd;
16
      level = l;
17
    }
18
  }
19

20
  public List<List<Integer>> verticalTraversal(TreeNode root) {
21
    Map<Integer, PriorityQueue<MNode>> map = new TreeMap<>();
22
    Queue<MNode> q = new LinkedList<>();
23

24
    q.add(new MNode(root, 0, 0));
25

26
    while (!q.isEmpty()) {
27

28
      MNode curr = q.poll();
29
      if (map.containsKey(curr.hDist)) map.get(curr.hDist).add(curr);
30
      else {
31
        PriorityQueue<MNode> pq =
32
            new PriorityQueue<>(
33
                (a, b) -> (a.level == b.level) ? a.Node.val - b.Node.val : a.level - b.level);
34
        pq.add(curr);
35
        map.put(curr.hDist, pq);
36
      }
37

38
      if (curr.Node.left != null) q.add(new MNode(curr.Node.left, curr.hDist - 1, curr.level + 1));
39

40
      if (curr.Node.right != null)
41
        q.add(new MNode(curr.Node.right, curr.hDist + 1, curr.level + 1));
42
    }
43

44
    List<List<Integer>> ans = new ArrayList<>();
45
    for (Integer key : map.keySet()) {
46
      List<Integer> temp = new ArrayList<>();
47
      while (!map.get(key).isEmpty()) {
48
        temp.add(map.get(key).poll().Node.val);
49
      }
50
      ans.add(new ArrayList<>(temp));
51
    }
52

53
    return ans;
54
  }
55
}