314. Binary Tree Vertical Order Traversal

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]
   ]
   

Solution:

The idea is to level order traverse the tree and for each node we assign a weight to it.

We first assign root with weight 0.

For any given node with weight w, we assign w - 1 to its left child and w + 1 to its right child.

In this way, we level order traverse all the nodes, and put all the nodes to their assigned weight list.

Finally, we add all lists to the result.



Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> nodes = new LinkedList<>();
        Queue<Integer> weights = new LinkedList<>();
        nodes.offer(root);
        weights.offer(0);
        int max = 0;
        int min = 0;
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            int weight = weights.poll();
            if (!map.containsKey(weight)) {
                map.put(weight, new ArrayList<Integer>());
            }
            map.get(weight).add(node.val);
            max = Math.max(max, weight);
            min = Math.min(min, weight);
            if (node.left != null) {
                nodes.offer(node.left);
                weights.offer(weight - 1);
            }
            if (node.right != null) {
                nodes.offer(node.right);
                weights.offer(weight + 1);
            }
        }
        for (int i = min; i <= max; i++) {
            result.add(map.get(i));
        }
        return result;
    }
}