Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal of its nodes’ values.
Constraints:
- The number of nodes in the tree is in the range [1, 100].
- 0 <= Node.val <= 100
Examples:
Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: The tree is: 3 / \ 9 20 / \ 15 7 The vertical order traversal is: 9 / \ 3 15 / \ 20 7
Solutions
Breadth-First Search (BFS)
Time: O(N)Space: O(N)
We use a queue to perform a breadth-first search (BFS) traversal of the tree. For each node, we also keep track of its column number. We use a map to store the nodes at each column. Finally, we construct the result by iterating over the columns in order.
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
if (!root) return {
}
;
queue<pair<TreeNode*, int>> q;
q.push({
root, 0}
);
map<int, vector<int>> m;
int min = 0, max = 0;
while (!q.empty()) {
auto [node, col] = q.front();
q.pop();
if (node) {
m[col].push_back(node->val);
min = std::min(min, col);
max = std::max(max, col);
q.push({
node->left, col - 1}
);
q.push({
node->right, col + 1}
);
}
}
vector<vector<int>> res;
for (int i = min;
i <= max;
++i) {
res.push_back(m[i]);
}
return res;
}
}
;Follow-up:
How would you modify the solution to handle the case where the tree is very large and does not fit in memory?
