987. Vertical Order Traversal of a Binary Tree

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def verticalTraversal(self, root):
        def verticalOrder(root): 
            dict1={}
            dict2={}
            def dfs(root,d):
                nonlocal dict1
                if root!=None:
                    dict1[root.val]=d
                    dfs(root.left,d-1)
                    dfs(root.right,d+1)
            dfs(root,0)
            mn=min(dict1.values())
            mx=max(dict1.values())
            
            l=2
            list1=[root,None]
            while l>1:
                temp=[]
                l2=0
                while list1[0]!=None:
                    temp.append(list1[0].val)
                    l2+=1
                    if list1[0].left:
                        list1.append(list1[0].left)
                        l+=1
                    if list1[0].right:
                        list1.append(list1[0].right)
                        l+=1
                    list1.pop(0)
                    l-=1
                list1.pop(0)
                list1.append(None)
                temp.sort()
                i=0
                while l2>0:
                    if dict1[temp[i]] in dict2:
                        dict2[dict1[temp[i]]].append(temp[i])
                    else:
                        dict2[dict1[temp[i]]]=[temp[i]]
                    i+=1
                    l2-=1
                
            list1=[]
            for i in range(mn,mx+1):
                if i in dict2:
                    list1.append(dict2[i])
            return list1
        return verticalOrder(root)