987. Vertical Order Traversal of a Binary Tree

• Time: $O(n\log n/k) = O(n\log n)$, where $k = \text{width(tree)}$
• Space: $O(n)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: vector> verticalTraversal(TreeNode* root) { vector> ans; map>> xToSortedPairs; // {x: {(-y, val)}} dfs(root, 0, 0, xToSortedPairs); for (const auto& [_, pairs] : xToSortedPairs) { vector vals; for (const pair& pair : pairs) vals.push_back(pair.second); ans.push_back(vals); } return ans; } private: void dfs(TreeNode* root, int x, int y, map>>& xToSortedPairs) { if (root == nullptr) return; xToSortedPairs[x].emplace(y, root->val); dfs(root->left, x - 1, y + 1, xToSortedPairs); dfs(root->right, x + 1, y + 1, xToSortedPairs); } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public List> verticalTraversal(TreeNode root) { List> ans = new ArrayList<>(); TreeMap> xToSortedPairs = new TreeMap<>(); // {x: {(-y, val)}} dfs(root, 0, 0, xToSortedPairs); for (List pairs : xToSortedPairs.values()) { Collections.sort(pairs, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); List vals = new ArrayList<>(); for (int[] pair : pairs) vals.add(pair[1]); ans.add(vals); } return ans; } private void dfs(TreeNode root, int x, int y, TreeMap> xToSortedPairs) { if (root == null) return; xToSortedPairs.putIfAbsent(x, new ArrayList<>()); xToSortedPairs.get(x).add(new int[] {y, root.val}); dfs(root.left, x - 1, y + 1, xToSortedPairs); dfs(root.right, x + 1, y + 1, xToSortedPairs); } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]: ans = [] xToNodes = collections.defaultdict(list) def dfs(node: Optional[TreeNode], x: int, y: int) -> None: if not node: return xToNodes[x].append((-y, node.val)) dfs(node.left, x - 1, y - 1) dfs(node.right, x + 1, y - 1) dfs(root, 0, 0) for _, nodes in sorted(xToNodes.items(), key=lambda item: item[0]): ans.append([val for _, val in sorted(nodes)]) return ans