如何做企业交易网站/搜索引擎广告形式有
题目：
给定一个二叉树，返回其结点 垂直方向(从上到下，逐列)遍历的值。
如果两个结点在同一行和列，那么顺序则为 从左到右。
示例 1：
输入: [3,9,20,null,null,15,7]
3
/\
/ \
9 20
/\
/ \
15 7
输出:
[
[9],
[3,15],
[20],
[7]
]
示例 2:
输入: [3,9,8,4,0,1,7] 3
/\
/ \
9 8
/\ /\
/ \ / \
4 0 1 7
输出:
[
[4],
[9],
[3,0,1],
[8],
[7]
]
示例 3:
输入: [3,9,8,4,0,1,7,null,null,null,2,5](注意：0 的右侧子节点为 2，1 的左侧子节点为 5)
3
/\
/ \
9 8
/\ /\
/ \/ \
4 01 7
/\
/ \
5 2
输出:
[
[4],
[9,5],
[3,0,1],
[8,2],
[7]
]
解答：
最近一直准备春招，天天看C++操作系统计算机网络，都好久没刷题了，中等题都做不出来。想了半天觉得应该和层次遍历有关，但又没有具体的思路。看了别人的答案恍然大悟：
垂直遍历，用一个横坐标来指示节点最终的位置就可以，大致意思是这样：
由于深度从小到大，所以考虑BFS层次遍历。这样先遍历层数少的，再遍历层数大的，天然满足深度从少到多的条件。
当然用DFS也可以做，但dfs形参中要保存当前的层数，防止最后出现先遍历到比较深的节点最终排在较浅节点的前面。
另外同一行中还有从左到右的限制，这个我们只要按层次遍历的顺序，每行从左到右去分别加入左孩子、右孩子就可以满足这个限制条件。
BFS代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };*/
classSolution {public:
vector> verticalOrder(TreeNode*root) {if(root==nullptr){return{};
}
vector >res;
map >memo;
queuedata_queue;
queuecoordinate_queue;
data_queue.push(root);
coordinate_queue.push(0);
TreeNode* cur=nullptr;intcur_coor;while(not data_queue.empty()){
cur=data_queue.front(),cur_coor=coordinate_queue.front();
data_queue.pop(),coordinate_queue.pop();
memo[cur_coor].emplace_back(cur->val);//cur的值记录在横坐标为cur_coor的数组中
if(cur->left){
data_queue.push(cur->left);
coordinate_queue.push(cur_coor-1);
}if(cur->right){
data_queue.push(cur->right);
coordinate_queue.push(cur_coor+1);
}
}for(auto&pair:memo){
res.emplace_back(move(pair.second));
}returnres;
}
};
