/314. Binary Tree Vertical Order Traversal

314. Binary Tree Vertical Order Traversal

Medium
Hash Table57.8% acceptance

Given the root node of a binary tree, return a list of lists of node values representing the vertical order traversal of the tree. For each vertical column, nodes should be listed from top to bottom. If two nodes are in the same row and column, order them from left to right.

Example 1

Input: TreeNode(10, TreeNode(7, None, TreeNode(8)), TreeNode(13, TreeNode(12), TreeNode(15)))

Output: [[7],[10,12],[8,13],[15]]

Explanation: Vertical columns: leftmost [7], next [10,12], next [8,13], rightmost [15].

Example 2

Input: TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(7, None, TreeNode(9)))

Output: [[2],[3],[5,4,7],[9]]

Explanation: Vertical columns: [2], [3], [5,4,7], [9].

Constraints

  • 1 <= number of nodes <= 1000
  • -1000 <= node value <= 1000
Python (current runtime)

Case 1

Input: TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))

Expected: [[4],[2],[1,5,3],[6]]

Case 2

Input: TreeNode(20, TreeNode(10, None, TreeNode(15)), TreeNode(30, TreeNode(25), None))

Expected: [[10],[20,15,25],[30]]