Untitled

 avatar
unknown
java
10 days ago
1.6 kB
2
Indexable
import java.util.*;

// TreeNode definition as before

class Solution {
    public List<Integer> topView(TreeNode root) {
        // TreeMap to store the vertical level and its corresponding node
        TreeMap<Integer, Integer> map = new TreeMap<>();
        
        // Queue to store the node, vertical level
        Queue<Pair> q = new LinkedList<>();
        
        // Initialize the queue with the root node at vertical level 0
        q.offer(new Pair(root, 0));
        
        while (!q.isEmpty()) {
            Pair tuple = q.poll();
            TreeNode node = tuple.node;
            int vertical = tuple.vertical;
            
            // If this vertical level is not yet visited, add the node value
            if (!map.containsKey(vertical)) {
                map.put(vertical, node.val);
            }
            
            // Enqueue left and right child nodes with their respective vertical levels
            if (node.left != null) {
                q.offer(new Pair(node.left, vertical - 1)); // Left child goes to vertical - 1
            }
            if (node.right != null) {
                q.offer(new Pair(node.right, vertical + 1)); // Right child goes to vertical + 1
            }
        }
        
        // Prepare the result from the map
        List<Integer> result = new ArrayList<>(map.values());
        return result;
    }
}

class Pair {
    TreeNode node;
    int vertical;

    Pair(TreeNode node, int vertical) {
        this.node = node;
        this.vertical = vertical;
    }
}
Leave a Comment