Leetcode 1029 Solution

This article provides solution to leetcode question 1029 (vertical-order-traversal-of-a-binary-tree)

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

Solution

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None
class Solution: def verticalTraversal(self, root: TreeNode) -> List[List[int]]: m = collections.defaultdict(list)
q = [(root, 0)]
while q: s = len(q)
tmp = collections.defaultdict(list) for _ in range(s): node, x = q.pop(0) tmp[x].append(node.val)
if node.left: q.append((node.left, x - 1)) if node.right: q.append((node.right, x + 1))
for x, v in tmp.items(): m[x] += sorted(v)
ans = [] for x in sorted(m.keys()): v = m[x] ans.append(v) return ans