HashMap + BFS solution in Java


  • 0
    E

    The idea is quite straightforward: first store the vertical order of every node in a HashMap. Then use BFS to traverse the tree and add node values to the correct location of the list.

    Java code:

    public class Solution {
    private HashMap<TreeNode, Integer> nodeValColId;
    private List<List<Integer>> list;
    private int min, max;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        list = new ArrayList<>();
        
        if(root == null) return list;
    
        min = max = 0;
        nodeValColId = new HashMap<>();
        nodeValColId.put(root, 0);
        
        getNodeColId(root, 0);
    
        for(int i=min; i<=max; i++) {
            list.add(new ArrayList<>()); // initialize the list
        }
        
        // BFS traversal of the tree
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()) {
            TreeNode current = q.peek();
            q.poll();
            int level = nodeValColId.get(current);
            List<Integer> innerList = new ArrayList<>();
            innerList.add(current.val);
            list.get(level-min).add(current.val);
            if(current.left!=null)
                q.add(current.left);
            if(current.right!=null)
                q.add(current.right);
        }
        
        return list;
    }
    // compute the vertical order of all nodes
    private void getNodeColId(TreeNode root, int rootColId) {
        if(root.left!=null) {
            nodeValColId.put(root.left, rootColId-1);
            getNodeColId(root.left, rootColId-1);
            min = rootColId-1 < min ? rootColId-1 : min;
        }
        if(root.right!=null) {
            nodeValColId.put(root.right, rootColId+1);
            getNodeColId(root.right, rootColId+1);
            max = rootColId+1 > max ? rootColId+1 : max;
        }
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.