1
# Runtime: 69 ms (Top 15.25%) | Memory: 14.3 MB (Top 28.85%)
2
# Definition for a binary tree node.
3
# class TreeNode(object):
4
# def __init__(self, val=0, left=None, right=None):
5
# self.val = val
6
# self.left = left
7
# self.right = right
8
class Solution(object):
9
    def verticalTraversal(self, root):
10
        """
11
        :type root: TreeNode
12
        :rtype: List[List[int]]
13
        """
14
        q = [(0, 0, root)]
15
        l = []
16
        while q:
17
            col, row, node = q.pop()
18
            l.append((col, row, node.val))
19
            if node.left:
20
                q.append((col - 1, row + 1, node.left))
21
            if node.right:
22
                q.append((col + 1, row + 1, node.right))
23
        l.sort()
24
        print(l)
25
        ans = []
26
        ans.append([l[0][-1]])
27
        for i in range(1, len(l)):
28
            if l[i][0] > l[i - 1][0]:
29
                ans.append([l[i][-1]])
30
            else:
31
                ans[-1].append(l[i][-1])
32
        return ans