# 314. Binary Tree Vertical Order Traversal

Given a binary tree, return the  vertical order  traversal 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:

``````Input: [3,9,20,null,null,15,7]

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

Output:

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

Examples 2:

``````Input: [3,9,8,4,0,1,7]

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

Output:

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

Examples 3:

``````Input: [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

Output:

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

``````class Solution {
public:
vector<vector<int>> verticalOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root) return res;
map<int, vector<int>> m;
queue<pair<int, TreeNode*>> q;
q.push({0, root});
while (!q.empty()) {
auto a = q.front(); q.pop();
m[a.first].push_back(a.second->val);
if (a.second->left) q.push({a.first - 1, a.second->left});
if (a.second->right) q.push({a.first + 1, a.second->right});
}
for (auto a : m) {
res.push_back(a.second);
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/314

Binary Tree Level Order Traversal

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

https://leetcode.com/problems/binary-tree-vertical-order-traversal/discuss/76401/5ms-Java-Clean-Solution

https://leetcode.com/problems/binary-tree-vertical-order-traversal/discuss/76508/3ms-java-solution-beats-100

https://leetcode.com/problems/binary-tree-vertical-order-traversal/discuss/76463/Using-HashMapBFS-Java-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation