package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

/**
 * https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
 */
public class Problem987 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<YValue>> map = new TreeMap<>();
        verticalTraversal(root, 0, 0, map);
        List<List<Integer>> answer = new ArrayList<>();
        map.forEach((key, value) -> {
            Collections.sort(value, (a, b) -> Integer.compare(b.y, a.y));
            List<Integer> sub = new ArrayList<>();
            for (YValue v : value) {
                sub.add(v.value);
            }
            answer.add(sub);
        });
        return answer;
    }

    private static class YValue {
        private final int y;
        private final int value;

        public YValue(int y, int value) {
            this.y = y;
            this.value = value;
        }

        @Override
        public String toString() {
            return y + " -> " + value;
        }
    }

    private static void verticalTraversal(TreeNode root, int x, int y,
                                          Map<Integer, List<YValue>> map) {
        if (root == null) {
            return;
        }
        if (!map.containsKey(x)) {
            map.put(x, new ArrayList<>());
        }
        map.get(x).add(new YValue(y, root.val));
        verticalTraversal(root.left, x - 1, y - 1, map);
        verticalTraversal(root.right, x + 1, y - 1, map);
    }

    public static void main(String[] args) {
        Problem987 prob = new Problem987();

        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(prob.verticalTraversal(root)); // [[9],[3,15],[20],[7]]

        root = new TreeNode(0);
        root.left = new TreeNode(8);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(3);
        root.right.left.right = new TreeNode(4);
        root.right.left.right.right = new TreeNode(7);
        root.right.right = new TreeNode(2);
        root.right.right.left = new TreeNode(5);
        root.right.right.left.left = new TreeNode(6);
        System.out.println(prob.verticalTraversal(root)); // [[8],[0,3,6],[1,4,5],[2,7]]

        root = new TreeNode(0);
        root.left = new TreeNode(2);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        root.left.left.left.right = new TreeNode(7);
        root.left.left.left.right.left = new TreeNode(10);
        root.left.left.left.right.right = new TreeNode(8);
        root.left.left.right = new TreeNode(5);
        root.left.left.right.left = new TreeNode(6);
        root.left.left.right.left.left = new TreeNode(11);
        root.left.left.right.left.right = new TreeNode(9);
        System.out.println(prob.verticalTraversal(root)); // [[4,10,11],[3,6,7],[2,5,8,9],[0],[1]]
    }
}

@@ -728,33 +728,216 @@
  -%3E 
-Integer.compare(b.y, a.y)
+%7B%0A                int cmp = Integer.compare(b.y, a.y);%0A                if (cmp == 0) %7B%0A                    return Integer.compare(a.value, b.value);%0A                %7D%0A                return cmp;%0A            %7D
 );%0A 
@@ -1350,111 +1350,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return y + %22 -%3E %22 + value;%0A        %7D
 %0A   
@@ -1745,32 +1745,32 @@
 1, y - 1, map);%0A
+
         vertical
@@ -1820,1569 +1820,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem987 prob = new Problem987();%0A%0A        TreeNode root = new TreeNode(3);%0A        root.left = new TreeNode(9);%0A        root.right = new TreeNode(20);%0A        root.right.left = new TreeNode(15);%0A        root.right.right = new TreeNode(7);%0A        System.out.println(prob.verticalTraversal(root)); // %5B%5B9%5D,%5B3,15%5D,%5B20%5D,%5B7%5D%5D%0A%0A        root = new TreeNode(0);%0A        root.left = new TreeNode(8);%0A        root.right = new TreeNode(1);%0A        root.right.left = new TreeNode(3);%0A        root.right.left.right = new TreeNode(4);%0A        root.right.left.right.right = new TreeNode(7);%0A        root.right.right = new TreeNode(2);%0A        root.right.right.left = new TreeNode(5);%0A        root.right.right.left.left = new TreeNode(6);%0A        System.out.println(prob.verticalTraversal(root)); // %5B%5B8%5D,%5B0,3,6%5D,%5B1,4,5%5D,%5B2,7%5D%5D%0A%0A        root = new TreeNode(0);%0A        root.left = new TreeNode(2);%0A        root.right = new TreeNode(1);%0A        root.left.left = new TreeNode(3);%0A        root.left.left.left = new TreeNode(4);%0A        root.left.left.left.right = new TreeNode(7);%0A        root.left.left.left.right.left = new TreeNode(10);%0A        root.left.left.left.right.right = new TreeNode(8);%0A        root.left.left.right = new TreeNode(5);%0A        root.left.left.right.left = new TreeNode(6);%0A        root.left.left.right.left.left = new TreeNode(11);%0A        root.left.left.right.left.right = new TreeNode(9);%0A        System.out.println(prob.verticalTraversal(root)); // %5B%5B4,10,11%5D,%5B3,6,7%5D,%5B2,5,8,9%5D,%5B0%5D,%5B1%5D%5D%0A    %7D
 %0A%7D%0A

Solve problem 987