987. Vertical Order Traversal of a Binary Tree

Loading...LeetCode

原本想 traversal one pass，发现解决不了同坐标不同值的排序问题，索性 traverse 完了再去生成结果。

核心还是DFS inorder，过程里用到 hash map和一些sort的技巧。

12/28/2020 Update:

DFS traverse 的时候就可以按 {x: [ (y1, value1), (y2, values)] } 的格式记录，节约之后 sort 整理的运算。

v1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        cords = collections.defaultdict(list)
        
        def inorder(node, x, y, t):
            if not node: return
            if node.left: inorder(node.left, x-1, y-1, t)
            t[(x, y)].append(node.val)
            if node.right: inorder(node.right, x+1, y-1, t)
            return t
        
        inorder(root, 0, 0, cords)
        cords = sorted(cords.items(), key=lambda item: (item[0][0], -item[0][1]))
        
        res = collections.defaultdict(list)
        for (x, y), v in cords:
            res[x].extend(sorted(v))
        return [x[1] for x in sorted(res.items())]

v2

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        record, res = collections.defaultdict(list), []
        
        def inorder(root: TreeNode, x, y):
            if not root: return
            inorder(root.left, x-1, y-1)
            record[x].append((y, root.val))
            inorder(root.right, x+1, y-1)
        
        inorder(root, 0, 0)
        
        for x in sorted(record.keys()):
            res.append([item[1] for item in sorted(record[x], key = lambda item: (-item[0], item[1]))])
            
        return res