BFS solution beating 90% in Python


  • 0
    U
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def verticalOrder(self, root):
            """
            :type root: TreeNode
            :rtype: List[List[int]]
            """
            ans = []
            hash = {}
            queue = [(root, 0)]
            while queue:
                x = queue.pop(0)
                if x[0] is None:
                    continue
                else:
                    if x[1] not in hash:
                        hash[x[1]] = [x[0].val]
                    else:
                        hash[x[1]].append(x[0].val)
                        
                    queue.append((x[0].left, x[1] - 1))
                    queue.append((x[0].right, x[1] + 1))
            
            keys = sorted(hash.keys())
            for key in keys:
                ans.append(hash[key])
            return ans
        
            
    

Log in to reply
 

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