Vertical Order Traverse

314. Binary Tree Vertical Order Traversal

# 使用一個min_idx紀錄最小的idx
def verticalOrder(self, root: TreeNode) -> List[List[int]]:
    record = defaultdict(list)
    min_idx = 0
    q = [(root, 0)]
    
    while q:
        node, idx = q.pop(0)
        if not node: continue
        min_idx = min(min_idx, idx)
        record[idx].append(node.val)
        q.append((node.left, idx-1))
        q.append((node.right, idx+1))
    
    ans = []
    
    for idx in sorted(record):
        ans.append(record[idx])
    
    return ans

987. Vertical Order Traversal of a Binary Tree

與上題不同的是，same position將按照increasing order 排列，需要紀錄x, y position的資料

def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
    position = defaultdict(lambda: defaultdict(list))
    q = [(root, 0, 0)]
    
    while q:
        node, x, y = q.pop(0)
        if not node: continue
        position[x][y].append(node.val)
        q.append((node.left, x-1, y+1))
        q.append((node.right, x+1, y+1))
    
    ans = []
    
    for x in sorted(position):
        container = []
        for y in sorted(position[x]):
            container += sorted(position[x][y])
        ans.append(container)
    
    return ans