MUYANG GUO / INDEX

LeetCode

LeetCode 314 Binary Tree Vertical Order Traversal - Medium

314. Binary Tree Vertical Order Traversal -- Medium

·2 min read·#LeetCode#Medium#Python

314. Binary Tree Vertical Order Traversal — Medium

Open on LeetCode

Problem

  1. Binary Tree Vertical Order Traversal -- Medium

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

3 /
/
9 20 /
/
15 7

Output:

[ [9], [3,15], [20], [7] ] Examples 2:

Input: [3,9,8,4,0,1,7]

 3
/\

/
9 8 /\ /
/ /
4 01 7

Output:

[ [4], [9], [3,0,1], [8], [7] ] Examples 3:

Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)

 3
/\

/
9 8 /\ /
/ /
4 01 7 /
/
5 2

Output:

[ [4], [9,5], [3,0,1], [8,2], [7] ]

Solution

### BFS and avoid sorting:
 
# 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 verticalOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
 
        columnTable = defaultdict(list)
        min_column = max_column = 0
        queue = deque([(root, 0)])
 
        while queue:
            node, column = queue.popleft()
            if node is not None:
                columnTable[column].append(node.val)
                min_column = min(min_column, column)
                max_column = max(max_column, column)
                queue.append((node.left, column - 1))
                queue.append((node.right, column + 1))
 
        return [columnTable[x] for x in range(min_column, max_column + 1)]
 
 
 
### DFS version:
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import defaultdict
class Solution:
    def verticalOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
 
        columnTable = defaultdict(list)
        min_column = max_column = 0
 
        def DFS(node, row, column):
            if node is not None:
                nonlocal min_column, max_column
                columnTable[column].append((row, node.val))
                min_column = min(min_column, column)
                max_column = max(max_column, column)
 
                # preorder DFS
                DFS(node.left, row + 1, column - 1)
                DFS(node.right, row + 1, column + 1)
 
        DFS(root, 0, 0)
        # order by column and sort by row
        ret = []
        for col in range(min_column, max_column + 1):
            columnTable[col].sort(key=lambda x:x[0])
            colVals = [val for row, val in columnTable[col]]
            ret.append(colVals)
 
        return ret

Comments