vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> results;
if (root == NULL)
return results;
map<int, vector<int>> records;
queue<pair<TreeNode *, int>> nodes;
nodes.push(make_pair(root, 0));
while (nodes.size()) {
TreeNode *root = nodes.front().first;
int current = nodes.front().second;
nodes.pop();
records[current].push_back(root>val);
if (root>left) {
nodes.push(make_pair(root>left, current  1));
}
if (root>right) {
nodes.push(make_pair(root>right, current + 1));
}
}
for (auto record : records) {
results.push_back(record.second);
}
return results;
}
Clean c++ BFS solution


I had exactly same solution as yours! However, since
std::map
is ordered STL container, every query operator[]
runsO(log N)
time, so the overall time complexity will beO(N*logN)
, whereN
is the number of nodes in the tree.
As some optimized solutions posted by others, an improvement can be made by usingstd::unordered_map
to store index to node values. The trick is that, eventually, the indices must continuously cover a range. So just keep tracking the max and min indices while writing records. Finally, a traversal from min index to max index instd::unordered_map
will return the desired result. The improved time complexity isO(N)
.
