987. Vertical Order Traversal of a Binary Tree

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

solution

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        mydict = collections.defaultdict(list)
        queue = collections.deque()
        queue.append([root, 0, 0])
        
        while queue:
            node, h, w = queue.popleft()
            mydict[w].append([h, node.val])

            if node.left:
                queue.append([node.left, h+1, w-1])
            if node.right:
                queue.append([node.right, h+1, w+1])
        
        res = []
        for key in sorted(mydict):
            values = mydict[key]
            values.sort(key=lambda x: (x[0], x[1]))
            res.append([x[1] for x in values])
        return res

时间复杂度：O(nlog(n)) 空间复杂度：O(n)

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        mydict = collections.defaultdict(list)
        self.dfs(root, 0, 0, mydict)
        result = []
        for i in sorted(mydict.keys()):
            temp = []
            for j in sorted(mydict[i]):  # top to bottom顺序，所以也要记录level
                temp.append(j[1])
            result.append(temp)
        return result
    
    def dfs(self, root, distance, level, mydict):
        if not root:
            return
        mydict[distance].append((level, root.val))
        self.dfs(root.left, distance - 1, level + 1, mydict)
        self.dfs(root.right, distance + 1, level + 1, mydict)