Leetcode(314) Binary Tree Vertical Order Traversal

发表于 | 分类于

Description

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:

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

Examples 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

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

Examples 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]
]

解法

在TreeNode外包装一层level，然后通过BFS扫描（不能用前序遍历因为有顺序问题，必须是从上往下的），这里采用TreeMap保证已按Level排好序，遍历输出到list即可。

具体代码如下：

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
59
60
61
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: the root of tree
     * @return: the vertical order traversal
     */
     List<List<Integer>> res = new ArrayList<>();
     TreeMap<Integer,List> map = new TreeMap<>();
    public List<List<Integer>> verticalOrder(TreeNode root) {
        // write your code here
        if(root == null){
            return null;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(root,0));
        while(!q.isEmpty()){
            Node now = q.poll();
            if(map.containsKey(now.level)){
                map.get(now.level).add(now.realnode.val);
            }
            else{
                List<Integer> tmp = new ArrayList<>();
                tmp.add(now.realnode.val);
                map.put(now.level,tmp);
            }
            if(now.realnode.left!=null){
                Node left = new Node(now.realnode.left,now.level - 1);
                q.offer(left);
            }
            if(now.realnode.right != null){
                Node right = new Node(now.realnode.right,now.level + 1);
                q.offer(right);
            }
        }
        Set<Integer> ks = map.keySet();
        Iterator it = ks.iterator();
        while(it.hasNext()){
            res.add(map.get(it.next()));
        }
        return res;
    }
    class Node{
        TreeNode realnode;
        int level;
        Node(TreeNode realnode,int level){
            this.realnode = realnode;
            this.level = level;
        }
    }
}