314. Binary Tree Vertical Order Traversal

Problem:

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples:

1. Given binary tree [3,9,20,null,null,15,7],
   

      3
     /\
    /  \
    9  20
       /\
      /  \
     15   7
   

   return its vertical order traversal as:

   [
     [9],
     [3,15],
     [20],
     [7]
   ]
   

2. Given binary tree [3,9,8,4,0,1,7],
   

        3
       /\
      /  \
      9   8
     /\  /\
    /  \/  \
    4  01   7
   

   return its vertical order traversal as:

   [
     [4],
     [9],
     [3,0,1],
     [8],
     [7]
   ]
   

3. 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),
   

        3
       /\
      /  \
      9   8
     /\  /\
    /  \/  \
    4  01   7
       /\
      /  \
      5   2
   

   return its vertical order traversal as:

   [
     [4],
     [9,5],
     [3,0,1],
     [8,2],
     [7]
   ]

7/5/2018 update:
To further optimize the solution. Use another queue to keep tracking of column.
Similar problem: Maximum Width of Binary Tree

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        queue.offer(root);
        cols.offer(0);
        
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int col = cols.poll();
            map.computeIfAbsent(col, k -> new ArrayList<>()).add(cur.val);
            max = Math.max(col, max);
            min = Math.min(col, min);
            
            if (cur.left != null) {
                queue.offer(cur.left);
                cols.offer(col - 1);
            }
            
            if(cur.right != null) {
                queue.offer(cur.right);
                cols.offer(col + 1);
            }
        }
        
        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }
        return res;
    }
}

--------------------------------------------------------------------------------------------------------------------------
6/13/2018 update:
How to order the result lists from left to right? While BFS, keep tracking of min and max column indexes. Then get from map from min to max.

class Solution {
    class Pair {
        int index;
        TreeNode node;
        public Pair(int index, TreeNode node) {
            this.index = index;
            this.node = node;
        }
        
    }
    public List<List<Integer>> verticalOrder(TreeNode root) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<Pair> queue = new LinkedList<>();
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        if (root == null) return res;
        queue.offer(new Pair(0, root));
        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            map.computeIfAbsent(cur.index, k -> new ArrayList<>()).add(cur.node.val);
            min = Math.min(min, cur.index);
            max = Math.max(max, cur.index);
            if (cur.node.left != null) {
                queue.offer(new Pair(cur.index - 1, cur.node.left));
            }

            if (cur.node.right!= null) {
                queue.offer(new Pair(cur.index + 1, cur.node.right));
            }
        }

        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }
        return res;
    }
}

--------------------------------------------------------------------------------------------------------------------------
Analysis:
If the node are on the same column, then follow BFS. Use Tree Map column as key, list of nodes' value as value. We can sort by column easily with treemap, but sarifice efficiency.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class Pair {
        int index;
        TreeNode node;
        public Pair(int index, TreeNode node) {
            this.index = index;
            this.node = node;
        }
        
    }
    public List<List<Integer>> verticalOrder(TreeNode root) {
        Map<Integer, List<Integer>> map = new TreeMap<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<Pair> queue = new LinkedList<>();
        if (root == null) return res;
        queue.offer(new Pair(0, root));
        
        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            TreeNode node = cur.node;
            int index = cur.index;
            map.computeIfAbsent(index, k -> new ArrayList<>()).add(node.val);
            if (node.left != null) {
                queue.offer(new Pair(index - 1, node.left));        
            }
            if (node.right != null) {
                queue.offer(new Pair(index + 1, node.right));       
            }
        }
        
        for (int key: map.keySet()) {
            res.add(map.get(key));
        }
        
        return res;
    }
}