Leetcode 1029 Solution

This article provides solution to leetcode question 1029 (vertical-order-traversal-of-a-binary-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 1029" in your browser address bar if you have bunnylol configured.

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