Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position 

(X, Y)

, its left and right children respectively will be at positions 

(X-1, Y-1)

 and 

(X+1, Y-1)

.

Running a vertical line from 

X = -infinity

 to 

X = +infinity

, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing 

Y

 coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of 

X

 coordinate.  Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).
           

思路：这题跟314 Binary Tree Vertical Order Traversal 不同的是：

Difference:

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

987. If two nodes have the same position, then the value of the node that is reported first is the value that is smaller. 

When two nodes have the same position (i.e. same X and same Y value), 

314

 asks us to sort them in the result based on X ("from left to right"), while 

987

 asks us to sort them in the result based on the nodes' values.

方法就是加个不一样的comparator就可以解决问题了。代码由314 Binary Tree Vertical Order Traversal 更改得来。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private class Node {
        public int x;
        public int y;
        public TreeNode node;
        public Node(int x, int y, TreeNode node) {
            this.x = x;
            this.y = y;
            this.node = node;
        }
    }
    
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Queue<TreeNode> nqueue = new LinkedList<>();
        Queue<Integer> iqueue = new LinkedList<>();
        nqueue.offer(root);
        iqueue.offer(0);
        HashMap<Integer, List<Node>> hashmap = new HashMap<>();
        
        int level = 0; int minIndex = 0; int maxIndex = 0;
        while(!nqueue.isEmpty()) {
            int size = nqueue.size();
            for(int i = 0; i < size; i++) {
                TreeNode node = nqueue.poll();
                int index = iqueue.poll();
                minIndex = Math.min(minIndex, index);
                maxIndex = Math.max(maxIndex, index);
                hashmap.putIfAbsent(index, new ArrayList<Node>());
                hashmap.get(index).add(new Node(level, index, node));
                
                if(node.left != null) {
                    nqueue.offer(node.left);
                    iqueue.offer(index - 1);
                }
                
                if(node.right != null) {
                    nqueue.offer(node.right);
                    iqueue.offer(index + 1);
                }             
            }
            level++;
        }
        
        for(int i = minIndex; i <= maxIndex; i++) {
            List<Node> list = hashmap.get(i);
            Collections.sort(list, (a, b) -> {
                if(a.x != b.x) {
                    return a.x - b.x;
                } else {
                    if(a.y != b.y) {
                        return a.y - b.y;
                    } else {
                        return a.node.val - b.node.val;
                    }
                }
            });
            List<Integer> templist = new ArrayList<>();
            for(Node n: list) {
                templist.add(n.node.val);
            }
            res.add(templist);
        }
        return res;
    }
}