314 Binary Tree Vertical Order Traversal

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:

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

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

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

Company Tag: Google Snapchat Facebook

分析&代码

这个题不难，但是挺有趣的。

• 就是在每个递归的时候，传一个index进去，如果根节点是0，那么左子树就是-1，右子树就是1。 左子树的左子树就是-1，左子树的右子树就是0，etc

• 然后这道题还有一个坑，就是要level order，所以必须bfs，如果dfs递归的话，相同的index的节点输出的顺序可能就会反了。

• 其实这道题是我上个月刷的时候做的，但是今天重新做了发现没有写过。之前的做法是正反两个map，node2index+index2node，这样正反存，但是感觉写起来比较丑。 我这次写的时候把index+TreeNode打包成一个新的类，这样只用当做普通的node来处理就行了。

• 还有要说的一个点就是，因为map里面的index是没有顺序的，我们最后结果要按照index顺序输出，所以可以在遍历的时候就维持一个index的最小值和最大值。

class Node {
    int index;
    TreeNode root;
    public Node(int index, TreeNode root) {
        this.index = index;
        this.root = root;
    }
}

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if(root == null) {
        return res;
    }
    int[] minMax = new int[2];
    minMax[0] = Integer.MAX_VALUE;
    minMax[1] = Integer.MIN_VALUE;
    Map<Integer, List<Integer>> map = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();
    Node nodeRoot = new Node(0, root);
    queue.offer(nodeRoot);
    while(!queue.isEmpty()) {
        Node cur = queue.poll();
        List<Integer> list = map.get(cur.index);
        if(list == null) {
            list = new ArrayList<Integer>();
        }
        list.add(cur.root.val);
        map.put(cur.index, list);
        minMax[0] = Math.min(minMax[0], cur.index);
        minMax[1] = Math.max(minMax[1], cur.index);
        if(cur.root.left != null) {
            Node left = new Node(cur.index - 1, cur.root.left);
            queue.offer(left);
        }
        if(cur.root.right != null) {
            Node right = new Node(cur.index + 1, cur.root.right);
            queue.offer(right);
        }
    }
    for(int i = minMax[0]; i <= minMax[1]; i++) {
        res.add(map.get(i));
    }
    return res;
}