Python BFS+DFS


  • 0

    use DFS to get the left and right bounds, BFS to put them into the correct column buckets.

    class Solution(object):
        def verticalOrder(self, root):
            if not root: return []
            lr = [0,0]
            def bound(node,col):
                if not node: return
                lr[0] = min(lr[0],col)
                lr[1] = max(lr[1],col)
                bound(node.left,col-1)
                bound(node.right,col+1)
            bound(root,0)
            ans = [[] for _ in xrange(lr[1]-lr[0]+1)]
            q = collections.deque([(root,0-lr[0])])
            while q:
                node, c = q.popleft()
                ans[c] += node.val,
                if node.left:
                    q.append((node.left,c-1))
                if node.right:
                    q.append((node.right,c+1))
            return ans

Log in to reply
 

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