Untitled

 avatar
unknown
java
5 months ago
1.8 kB
2
Indexable
import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    // Using TreeMap for ordered keys, and TreeMap with TreeSet for ordered values in sub-maps
    private Map<Integer, Map<Integer, TreeSet<Integer>>> m = new TreeMap<>();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Queue<Tuple> q = new LinkedList<>();
        q.offer(new Tuple(root, 0, 0));

        // Perform BFS to populate the map with x and y coordinates
        while (!q.isEmpty()) {
            Tuple current = q.poll();
            TreeNode temp = current.node;
            int x = current.x;
            int y = current.y;
            
            // Place the value in the nested map structure
            m.putIfAbsent(x, new TreeMap<>());
            m.get(x).putIfAbsent(y, new TreeSet<>());
            m.get(x).get(y).add(temp.val);

            if (temp.left != null) {
                q.offer(new Tuple(temp.left, x - 1, y + 1));
            }
            if (temp.right != null) {
                q.offer(new Tuple(temp.right, x + 1, y + 1));
            }
        }

        // Create the answer list based on the ordered structure of the map
        List<List<Integer>> ans = new ArrayList<>();
        for (Map<Integer, TreeSet<Integer>> map : m.values()) {
            List<Integer> col = new ArrayList<>();
            for (TreeSet<Integer> nodes : map.values()) {
                col.addAll(nodes);
            }
            ans.add(col);
        }

        return ans;
    }
}

// Helper class for queue items
class Tuple {
    TreeNode node;
    int x, y;

    Tuple(TreeNode node, int x, int y) {
        this.node = node;
        this.x = x;
        this.y = y;
    }
}
Editor is loading...
Leave a Comment