Concise Python solution using BFS, O(n) time and O(n) space


  • 0
    C

    My idea here is to assign an index to each node, the root is indexed zero, its left nodes have indexes less than zero, and its right nodes have indexes greater than zero, and then the final result is grouped by indexes, nodes with same index will be put into the same bucket.

    As the question requests us to travel from top to bottom and left to right, level traveling is the only traversal method to do that, that's why I use BFS to travel the tree.

    import collections
    def verticalOrder(root):
            if not root:
                return []
                
            mp = {}
            rows = []
            queue = collections.deque()
            queue.append((root, 0))
            while queue:
                node, idx = queue.popleft()
                if node.left:
                    queue.append((node.left, idx - 1))
                if node.right:
                    queue.append((node.right, idx + 1))
                if idx not in mp:
                    mp[idx] = []
                mp[idx].append(node.val)
                
            minKey, maxKey = float('inf'), float('-inf')
            for key in mp.keys():
                minKey = min(minKey, key)
                maxKey = max(maxKey, key)
                
            ret = [None] * (maxKey - minKey + 1)
            for key, lst in mp.items():
                ret[key - minKey] = lst
                
            return ret

  • 0

    That's only O(n^2), not O(n). Because pop(0) takes linear time.


  • 0
    C

    Thanks StefanPochmann, I've changed it to collections.deque, sometimes details are very important, it's good that someone points out when you are too focus on something else:)


  • 0
    L

    nice solution! thanks!

    But I wonder what's the time complexity difference of pop() operation between list and deque


Log in to reply
 

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