(314 followup) 987. Vertical Order Traversal of a Binary Tree

T: O(n)
S: O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }

 0 1 2 3

 3/2 = 1

(x) wrong idea: (root is not always in the center)
 dfs to find max and min index (root is 0)
 then we'll know the width of result list,
 then dfs again to put data

Correct idea:
similar to 314
 so we have to find tree width range -> min max 
 and because this question is asking to add result when row level is the same, value needs to sort
 so in map we have col, List<Step(val, row)>
when row is the same sort by val, or sort by row

T: O(n)
S: O(n)
 */
class Solution {
    private record Step(int value, int row){};
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        int[] minMax = new int[2];
        Map<Integer, List<Step>> map = new HashMap<>(); // colIndex, node value
        dfs(root, 0, 0, minMax, map);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = minMax[0]; i <= minMax[1]; i++) {
            List<Step> list = map.get(i);
            Collections.sort(list, (a, b) -> {
                if (a.row == b.row) {
                    return a.value - b.value;
                }
                return a.row - b.row;
            });
            List<Integer> rs = new ArrayList<>();
            for (Step s : list) {
                rs.add(s.value);
            }
            result.add(rs);
        }
        return result;
    }

    private void dfs(TreeNode node, int row, int col, int[] minMax, Map<Integer, List<Step>> map) {
        if (node == null) {
            return;
        }
        map.computeIfAbsent(col, k -> new ArrayList<>()).add(new Step(node.val, row));
        minMax[0] = Math.min(minMax[0], col);
        minMax[1] = Math.max(minMax[1], col);
        dfs(node.left, row+1, col-1, minMax, map);
        dfs(node.right, row+1, col+1, minMax, map);
    }
}