[LC 451] Binary Tree Vertical Order Traversal

关键一部是理解vertical order到底是怎么排序的。画出下图很重要(图片来自discussion):
stock-photo-135826875
这就可以看出排序的规律,如果一个node的column是col,那么它的left child的column就是col-1,right child的column就是col+1. 明白这一点,题就解了一半。然后就想到需要一个map来存每个column对应的所有node,而且还需要保存同一个column所有node的顺序,所以这个map是Map<Integer, List<Integer>>。为了找到所有node的column,需要遍历整个tree,所以需要一个queue存node。同时,在遍历到某一个node时,需要知道当前node对应的column,以此来判断当前node的left child和right child都对应哪个column,所以需要另外一个queue,对应存储node的column。一开始想到用一个Map<TreeNode, Integer>来存node到column的对应。注意到这个map和之前的map不能合二为一,因为第二个map不能保存key也就是node的顺序,这样如果最后把Map<TreeNode, Integer>转化成最终结果List<List<Integer>>, 某一个column对应的List<Integer>可能是乱序的。
这道题一开始可能不能完全想清楚都需要哪些variable来存储必要的中间结果。
public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) return res;
        
        Map<Integer, List<Integer>> map = new HashMap(); // what map should store to maintain the order of nodes in each column
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        Queue<Integer> colq = new LinkedList<Integer>(); // needs a queue for columns, to determine which column the current node belongs to, so in the iteration we can further determine the left and right child’s column number
        
        q.add(root);
        colq.add(0);
        
        int minCol = Integer.MAX_VALUE;
        int maxCol = Integer.MIN_VALUE;
        
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            int col = colq.poll();
            
            if (!map.containsKey(col)) {
                map.put(col, new ArrayList<Integer>());
            }
            map.get(col).add(node.val);
            
            minCol = Math.min(minCol, col);
            maxCol = Math.max(maxCol, col); // needs a maxCol to determine the size of the result (list of list)
            
            if (node.left != null) {
                q.add(node.left);
                colq.add(col-1);
            }
 
            if (node.right != null) {
                q.add(node.right);
                colq.add(col+1);
            }
        }
        for (int i = minCol; i <= maxCol; i++) {
            res.add(map.get(i));
        }
        return res;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s