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
2
3
4
5
6
7
8
Given binary tree [3,9,20,null,null,15,7],
   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7

return its vertical order traversal as:

1
2
3
4
5
6
[
  [9],
  [3,15],
  [20],
  [7]
]

Given binary tree [3,9,8,4,0,1,7],

1
2
3
4
5
6
7
    3
   /\
  /  \
  9   8
 /\  /\
/  \/  \
4  01   7

return its vertical order traversal as:

1
2
3
4
5
6
7
[
  [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),

1
2
3
4
5
6
7
8
9
10
    3
   /\
  /  \
  9   8
 /\  /\
/  \/  \
4  01   7
   /\
  /  \
  5   2

return its vertical order traversal as:

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

解法1：

一种BFS的增强用法
在每次push一个node到一个queue的同时，维护另外一个queue，记录相对应的node的信息
用一个hashmap记录每一个col对应的答案。
然后min，max记录col的范围，之后把map里的数字再按顺序读取就可以了
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 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) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();  // record each column's result
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); // used for bfs search
        Queue<Integer> column = new LinkedList<Integer>();  // used for bfs search, update each node's column number
        queue.offer(root);
        column.offer(0);
        int min = 0;
        int max = 0;
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            int col = column.poll();
            min = Math.min(col, min);
            max = Math.max(col, max);
            if (!map.containsKey(col)) {
                map.put(col, new ArrayList<Integer>());
            }
            map.get(col).add(current.val);
            if (current.left != null) {
                queue.offer(current.left);
                column.offer(col - 1);
            }
            if (current.right != null) {
                queue.offer(current.right);
                column.offer(col + 1);
            }
        }
        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }
        return res;
    }
}