leetcode314

Posted on | In

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:

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

Idea

the order:
Say, in example2,
[3, 0, 1], include the order from layer-layer and left-right in the same layer, which the bfs may achieve the requirement. Since, we may need the order vertical, we can perform bfs on a col que as well as nodes.

Code

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
class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        que_node = [root]
        que_col = [0]
        dic_ = collections.defaultdict(list)
        dic_[0].append(root.val)
        
        while que_node:
            h = que_node.pop(0)
            c = que_col.pop(0)
            
            if h.left:
                que_node.append(h.left)
                que_col.append(c - 1)
                dic_[c - 1].append(h.left.val)
                
            if h.right:
                que_node.append(h.right)
                que_col.append(c + 1)
                dic_[c + 1].append(h.right.val)
        res = []
        for i in sorted(dic_.keys()):
            res.append(dic_[i])
            
        return res