GuilinDev

Lc0314

05 August 2008

314 Binary Tree Vertical Order Traversal $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Input: [3,9,20,null,null,15,7]

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

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]

树形结构的从左向右Traversal - BFS

  • BFS, put node, col into queue at the same time
  • Every left child access col - 1 while right child col + 1
  • This maps node into different col buckets
  • Get col boundary min and max on the fly
  • Retrieve result from cols

O(n)

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

  class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>(); // 存nodes
        Queue<Integer> cols = new LinkedList<>(); //存列数信息

        q.add(root); 
        cols.add(0);

        int min = 0;
        int max = 0;

        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            int col = cols.poll();

            if (!map.containsKey(col)) {
                map.put(col, new ArrayList<Integer>());
            }
            map.get(col).add(node.val);

            if (node.left != null) {
                q.add(node.left); 
                cols.add(col - 1);
                min = Math.min(min, col - 1);
            }

            if (node.right != null) {
                q.add(node.right);
                cols.add(col + 1);
                max = Math.max(max, col + 1);
            }
        }

        for (int i = min; i <= max; i++) {
            res.add(map.get(i));
        }

        return res;
    }
  }

DFS

Say root has position d, then root.left has position d - 1 and root.right has position d + 1.

Do DFS with inorder traversal, so that left children get explored first before right children (left has to come first as required by the question).

Sort by position first, then by depth. If two nodes share the same position and depth, then due to 2, left node will come first.

O(nlogn)

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

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<int[]> data = new ArrayList<>();
        dfs(root, 0, 0, data);
        data.sort((a, b) -> a[0] == b[0]? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
        
        List<List<Integer>> ans = new ArrayList<>();
        int prev = Integer.MIN_VALUE;
        for (int[] d : data){
            if (prev != d[0]){
                List<Integer> next = new ArrayList<>(List.of(d[2]));
                ans.add(next);
                prev = d[0];
            }else{
                ans.get(ans.size() - 1).add(d[2]);
            }
        }
        return ans;
    }

    private void dfs(TreeNode root, int p, int l, List<int[]> data){
        if (root == null) return;
        data.add(new int[]{p, l, root.val});
        dfs(root.left , p - 1, l + 1, data);
        dfs(root.right, p + 1, l + 1, data);
    }
}
This site is open source. Improve this page.