Python Solution with Comments - Using Map and Queue


  • 0
    A
    import collections 
    
    class Solution(object):
        def verticalOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            # queue to traverse tree by level
            q = []
            # map to store columns and their values
            mp = collections.defaultdict(list)
            q.append((root, 0))
            while q:
                node, node_col = q[0] # decompose the first item in the queue
                q = q[1:]
                if node:
                    mp[node_col].append(node.val)
                    q.append((node.left, node_col - 1))
                    q.append((node.right, node_col + 1))
            
            res = []
            for key in sorted(mp):
                res.append(mp[key])
                
            return res
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.