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:

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]
]
Examples 3:

Input: [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

Output:

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

The algorithm for the question combines bfs and dfs

time O(n)

space O(n)

first call dfs(TreeNode root, int index) to find the number of total vertical layers for example, the root is at layer 0, and its left child is at layer -1, first we find out the boundary of the tree, after calling dfs, we get min = -1and max = 2

we need to store the

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

9   3,15  20  7
-1   0    1   2
we want to store the numbers in the corresponding answer array, but we don't have negative index
Answer Array
we first initialize the array 
for (int i = min; i <= max; i++ ){
  ans.add(new ArrayList<>());
}
index 0 : [9] 
index 1: [3, 15]  -> here is the first trick: we store (-min) as the index
index 2: [20]
index 3: [7]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int min;
    private int max;
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
        if (root == null) {
            return ans;
        }
        helper(root, 0);
        for (int i = min; i <= max; i++) {
            ans.add(new ArrayList<>());
        }
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> index = new LinkedList<>();
        queue.offer(root);
        index.offer(-min);
        while (!queue.isEmpty()) {
            TreeNode head = queue.poll();
            int idx = index.poll();
            ans.get(idx).add(head.val);
            if (head.left != null) {
                queue.offer(head.left);
                index.offer(idx - 1);
            }
            if (head.right != null) {
                queue.offer(head.right);
                index.offer(idx + 1);
            }
        }
        return ans;
    }
    //dfs to find the boundry min and max 
    public void helper(TreeNode root, int index) {
        if (root == null) {
            return;
        }
        min = Math.min(index, min);
        max = Math.max(index, max);
        helper(root.left, index - 1);
        helper(root.right, index + 1);
    }
}