Java level order traversal using extra information, detailed explanation with figure


  • 4
    Y

    The idea is just level-order traversal. Obviously we will need a queue to traversal the nodes level by level, but we will need to keep track of the vertical order, and in the result, the order should be sorted. We define another class Pair to keep track of the order information.

    public class Pair {
        TreeNode node;
        int order;
        public Pair(TreeNode n, int i) {
            node = n;
            order = i;
        }
    }
    

    Another question is how do we keep track of the result and sort if in the end. There are two ways. First is that we can just use a Map<Integer, List<Integer>> with the key as the order of the node, and the value the list of node values having the same order. To keep it sorted, we have use a TreeMap, which will naturally keep the entry sorted based on the key. Another way is during traversal, we can keep track of the min and max order of all the nodes, and in the end, add the map value to the result from the min value key to the max value key.

    As we traverse, if we go left, deduct 1 from the order. If we go right, add 1 to the order. For example, given binary tree [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5). The vertical level order as shown in the figure.
    enter image description here

    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        Queue<Pair> pairs = new LinkedList<>();
        pairs.offer(new Pair(root, 0));
        int min = 0;
        int max = 0;
        while(!pairs.isEmpty()) {
            Pair curr = pairs.poll();
            TreeNode node = curr.node;
            int order = curr.order;
            min = Math.min(min, order);
            max = Math.max(max, order);
            if(!map.containsKey(order)) {
                map.put(order, new ArrayList<>());
            }
            map.get(order).add(node.val);
            if(node.left != null) {
                pairs.offer(new Pair(node.left, order-1));
            }
            if(node.right != null) {
                pairs.offer(new Pair(node.right, order+1));
            }
        }
        for(int i = min; i <= max; i++) {
            if(map.containsKey(i)) {
                res.add(map.get(i));
            }
        }
        return res;
    }
    

Log in to reply
 

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