Python solution with O(n) time


  • 0
    M
    def verticalOrder_m3(self, root):
        # time: O(n)
        # space: O(n)
        queue = [(root, 0)]
        cols = {}
        mi, mx = 0, 0
        while queue:
            node, i = queue.pop(0)
            if i < mi: mi = i
            if i > mx: mx = i
            if node:
                if i not in cols:
                    cols[i] = []
                cols[i].append(node.val)
                queue += (node.left, i - 1), (node.right, i + 1)
        res = []
        for i in range(mi, mx + 1):
            if i in cols:
                res.append(cols[i])
        return res

Log in to reply
 

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