314.Binary Tree Vertical Order Traversal

Tags: [BFS], [level_by_level], [tree], [binary_tree], [col_by_col], [map]

Com: {fb}

Link: https://leetcode.com/problems/binary-tree-vertical-order-traversal/#/description

Given a binary tree, return thevertical ordertraversal 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. Given binary tree
   [3,9,20,null,null,15,7],

      3
     /\
    /  \
    9  20
       /\
      /  \
     15   7
   

   return its vertical order traversal as:

   [
     [9],
     [3,15],
     [20],
     [7]
   ]
   

2. Given binary tree
   [3,9,8,4,0,1,7],

        3
       /\
      /  \
      9   8
     /\  /\
    /  \/  \
    4  01   7
   

   return its vertical order traversal as:

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

3. Given binary tree
   [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
   

   return its vertical order traversal as:

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

More clean solution: BFS, Map, Col By Col

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []


        # root's col = 0
        # Use the col_to_val_map to record the col => [val1, val2, val3...]
        col_to_val_map = {}
        min_col = 0

        # BFS
        queue = deque()
        queue.append((root, 0))
        while queue:
            node, col = queue.popleft()
            min_col = min(min_col, col)
            if col not in col_to_val_map:
                col_to_val_map[col] = [node.val]
            else:
                col_to_val_map[col].append(node.val)

            if node.left:
                queue.append((node.left, col - 1))
            if node.right:
                queue.append((node.right, col + 1))

        result = []
        while min_col in col_to_val_map:
            result.append(col_to_val_map[min_col])
            min_col += 1

        return result

Note:

• In Python, if we do queue = deque((node, col)), the node will become the first element in the queue, and the col will become the second element in the queue. If we want the tuple (node, col) together be the first element of the queue, we should do queue = deque(), queue.append((node, col)).
• Time complexity = O(n), n is the number of nodes in the given tree.

Solution: BFS, Level By Level, Col By Col

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution(object):
    def verticalOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []

        # traverse tree level by level, and calculate the column number for each node:
        # root's col = 0
        levels = []
        level = []
        min_col = sys.maxint
        max_col = -sys.maxint - 1

        queue = deque()
        queue.append((root, 0))
        queue.append(None)

        while queue:
            curr = queue.popleft()
            if curr:
                node, col = curr
                min_col = min(min_col, col)
                max_col = max(max_col, col)
                level.append((node, col))

                if node.left:
                    queue.append((node.left, col - 1))
                if node.right:
                    queue.append((node.right, col + 1))
            else:
                # hit the end of the current level.
                levels.append(list(level))
                level = []

                if queue:
                    queue.append(None)

        num_of_cols = max_col - min_col + 1
        num_of_rows = len(levels)
        matrix = [[[] for _ in xrange(num_of_cols)] for _ in xrange(num_of_rows)]

        col_offset = -min_col
        for row in xrange(len(levels)):
            level = levels[row]
            for node, col in level:
                matrix[row][col + col_offset].append(node.val)

        result = []
        for col in xrange(num_of_cols):
            curr_col = []
            for row in xrange(num_of_rows):
                if not matrix[row][col]:
                    continue
                curr_col += matrix[row][col]
            result.append(list(curr_col))

        return result

Revelation:

• Set the root's col = 0, root.left's col = -1, root.right's col = 1, then root.left.left's col = -1 - 1 = -2, root.left.right's col = -1 + 1 = 0, root.right.left's col = 1 - 1 = 0, root.right.right's col = 1 + 1 = 2...

Note:

• Time complexity = O(n), n is the number of nodes in the given tree.