Question

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

Solution

  • Method 1: TreeMap + dfs ```Java /**
    • Definition for a binary tree node.
    • public class TreeNode {
    • int val;
    • TreeNode left;
    • TreeNode right;
    • TreeNode(int x) { val = x; }
    • } */ class Solution { private TreeMap<Integer, TreeMap<Integer, List>> treeMap; //outer key is the col number, inner key is the row number public List<List> verticalOrder(TreeNode root) { List<List> result = new ArrayList<>(); if(root == null) return result; this.treeMap = new TreeMap<>(); dfs(root, 0, 0); for(TreeMap<Integer, List> colMap: treeMap.values()){ List temp = new ArrayList<>(); for(List pos : colMap.values()){ temp.addAll(pos); } result.add(temp); } return result; } private void dfs(TreeNode node, int row, int col){ TreeMap<Integer, List> colMap = treeMap.containsKey(col) ? treeMap.get(col): new TreeMap<>(new Comparator(){ @Override public int compare(Integer a, Integer b){ return b - a; } }); List numbers = colMap.containsKey(row) ? colMap.get(row): new ArrayList<>(); numbers.add(node.val); colMap.put(row, numbers); treeMap.put(col, colMap); if(node.left != null) dfs(node.left, row - 1, col - 1); if(node.right != null) dfs(node.right, row - 1, col + 1); } } ```
  • Method 2: TreeMap + bfs ```Java /**
    • Definition for a binary tree node.
    • public class TreeNode {
    • int val;
    • TreeNode left;
    • TreeNode right;
    • TreeNode(int x) { val = x; }
    • } */ class Solution { private static class Node{ int col; TreeNode node; public Node(int col, TreeNode node){ this.col = col; this.node = node; } } public List<List> verticalOrder(TreeNode root) { List<List> result = new ArrayList<>(); if(root == null) return result; Map<Integer, List> map = new TreeMap<>(); Queue q = new LinkedList<>(); q.offer(new Node(0, root)); while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i < size; i++){ Node node = q.poll(); List list = map.containsKey(node.col) ? map.get(node.col): new ArrayList<>(); list.add(node.node.val); map.put(node.col, list); if(node.node.left != null) q.offer(new Node(node.col - 1, node.node.left)); if(node.node.right != null) q.offer(new Node(node.col + 1, node.node.right)); } } for(List list : map.values()){ result.add(list); } return result; } } ```