# 使用一個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