Python DFS and BFS with explaination


  • 0

    BFS version is straghtforward! BFS itself does a top to bottom traversal and what we need to do is to put horizontal position into account! Starting from 0, we minus 1 for left child and plus 1 for right child when dealing the horizontal position.

    class Solution(object):
    def verticalOrder(self, root):
        resNeg, resPos = [], []
        queue = collections.deque([(root,0)])
        while queue:
            curr = queue.popleft()
            if curr[0] is None:
                continue
            vpos = curr[1]
            if vpos >= 0:
                if vpos >= len(resPos):
                    resPos.append([])
                resPos[vpos].append(curr[0].val)
            else:
                negpos = -1 - vpos
                if negpos >= len(resNeg):
                    resNeg.append([])
                resNeg[negpos].append(curr[0].val)
            queue.append((curr[0].left, vpos - 1))
            queue.append((curr[0].right, vpos + 1))
        return resNeg[::-1] + resPos
    

    When DFS traverse the tree, we use a number to mark horizontal depth and vertical depth (i.e. key +- 1, depth +- 1). Just use a very simple pre-order traversal and then all nodes in the same column will be collected into the same list. Finally, sort the list horizontally and vertically according to the mark mentioned before. I think this solution can be even faster with some optimization.

    class Solution(object):
    def dfsHelper(self, root, key, dict, deep):
        if root:
            dict[key] = dict.get(key, [])
            dict[key].append((deep, root.val))
            self.dfsHelper(root.left, key - 1, dict, deep + 1)
            self.dfsHelper(root.right, key + 1, dict, deep + 1)
    
    def verticalOrder(self, root):
        array, dict = [], {}
        self.dfsHelper(root, 0, dict, 0)
        for k,v in dict.iteritems():
            v.sort(key=lambda x:x[0])
            array.append((k, [v[i][1] for i in xrange(0, len(v))]))
        array.sort(key=lambda x:x[0])
        return [array[i][1] for i in xrange(0, len(array))]

Log in to reply
 

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