[LeetCode 314] Binary Tree Vertical Order Traversal (Medium)

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:

Input: [3,9,20,null,null,15,7]

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

Output:

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

Examples 2:

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

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

Output:

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

Solution - BFS，给每个节点加上distance的属性。推入Queue的时候推入的是新的Node结构（带distance属性）

1. 以root为坐标起点，遍历整个树，找到每个点离root的距离
2. 比如9离root的距离是-1， 20的距离是1, 15是0, 7是2
3. 然后把距离相等的归类，最后就是

    0:【3,15】
    -1: [9]
    1: [20]
    2: [7]
    用treemap来存这个结构，以保证key是有序的

···
实际上就是BFS过程中，给每个node加一个distance的属性

• left child离ROOT的distance，是parent distance - 1
• right child离ROOT的distance，是parent distance + 1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
//     以root为坐标起点，遍历整个树，找到每个点离root的距离
//     比如9离root的距离是-1， 20的距离是1
//     15是0， 7是2
//     然后把距离相等的归类，最后就是
//     0:【3,15】
//     -1: [9]
//     1: [20]
//     2: [7]
//     用treemap来存这个结构，以保证key是有序的
    
//     实际上就是BFS过程中，给每个node加一个distance的属性
//     left child离ROOT的distance，是parent distance - 1
//     right child离ROOT的distance，是parent distance + 1
    
    static class Node {
        TreeNode node;
        int distance;
        
        public Node (TreeNode node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }
    
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<> ();
        if (root == null) {
            return result;
        }
        
        TreeMap<Integer, List<Integer>> tracker = new TreeMap<> ();
        Queue<Node> queue1 = new LinkedList<> ();
        Queue<Node> queue2 = new LinkedList<> ();
        
        queue1.add (new Node (root, 0));
        
        while (!queue1.isEmpty ()) {
            Node current = queue1.poll ();
            int currentNodeDistance = current.distance;
            TreeNode currentNode = current.node;
            
            List<Integer> list = tracker.getOrDefault (currentNodeDistance, new ArrayList<> ());
            list.add (currentNode.val);
            tracker.put (currentNodeDistance, list);
            
            if (currentNode.left != null) {
                queue2.add (new Node (currentNode.left, currentNodeDistance - 1));
            }
            
            if (currentNode.right != null) {
                queue2.add (new Node (currentNode.right, currentNodeDistance + 1));
            }
            
            if (queue1.isEmpty ()) {
                queue1 = queue2;
                queue2 = new LinkedList<> ();
            }
        }
        
        for (Map.Entry <Integer, List<Integer>> entry : tracker.entrySet ()) {
            result.add (entry.getValue ());
        }
        
        return result;
    }
}