# 987. Vertical Order Traversal of a Binary Tree 二叉树的垂序遍历

@TOC

## # 题目描述

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position `(X, Y)`, its left and right children respectively will be at positions `(X-1, Y-1)` and `(X+1, Y-1)`.

Running a vertical line from `X = -infinity` to `X = +infinity`, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing `Y` coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of `X` coordinate. Every report will have a list of values of nodes.

Example 1:

``````Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).
``````

Example 2:

``````Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.
``````

Note:

1. The tree will have between `1` and `1000` nodes.
2. Each node's value will be between `0` and `1000`.

## # 解题方法

### # DFS

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
nodeMap.clear();
dfs(root, 0, 0);
vector<vector<int>> res;
for (auto nm : nodeMap) {
sort(nm.second.begin(), nm.second.end());
vector<int> cols;
for (auto p : nm.second)
cols.push_back(p.second);
res.push_back(cols);
}
return res;
}
private:
map<int, vector<pair<int, int>>> nodeMap; // x ==> (-y, value)
void dfs(TreeNode* root, int x, int y) {
if (!root) return;
nodeMap[x].emplace_back(-y, root->val);
dfs(root->left, x - 1, y - 1);
dfs(root->right, x + 1, y - 1);
}
};
``````

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def verticalTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
self.m_ = list()
self.dfs(root, 0, 0)
self.m_.sort()
res = [[self.m_[0][2]]]
for i in range(1, len(self.m_)):
if self.m_[i][0] == self.m_[i - 1][0]:
res[-1].append(self.m_[i][2])
else:
res.append([self.m_[i][2]])
return res

def dfs(self, root, x, y):
if not root: return
self.m_.append((x, -y, root.val))
self.dfs(root.left, x - 1, y - 1)
self.dfs(root.right, x + 1, y - 1)
``````

### # BFS

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> verticalTraversal(TreeNode* root) {
queue<pair<TreeNode*, pair<int, int>>> q; // node, x, y
q.push(make_pair(root, make_pair(0, 0)));
map<int, vector<pair<int, int>>> nodeMap;
while (!q.empty()) {
auto d = q.front(); q.pop();
TreeNode* curNode = d.first;
int x = d.second.first;
int y = d.second.second;
nodeMap[x].emplace_back(-y, curNode->val);
if (curNode->left)
q.push(make_pair(curNode->left, make_pair(x - 1, y - 1)));
if (curNode->right)
q.push(make_pair(curNode->right, make_pair(x + 1, y - 1)));
}
vector<vector<int>> res;
for (auto nm : nodeMap) {
sort(nm.second.begin(), nm.second.end());
vector<int> cols;
for (auto p : nm.second)
cols.push_back(p.second);
res.push_back(cols);
}
return res;
}
};
``````

python版本的BFS如下，同样是先把所有的节点遍历一遍并保存每个节点的位置，然后根据位置再排序遍历求解的方式做到的。

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def verticalTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
q = collections.deque()
q.append((root, 0, 0))
m_ = list()
while q:
node, x, y = q.popleft()
m_.append((x, -y, node.val))
if node.left:
q.append((node.left, x - 1, y - 1))
if node.right:
q.append((node.right, x + 1, y - 1))
m_.sort()
res = [[m_[0][2]]]
for i in range(1, len(m_)):
if m_[i][0] == m_[i - 1][0]:
res[-1].append(m_[i][2])
else:
res.append([m_[i][2]])
return res
``````

## # 日期

2019 年 2 月 20 日 —— 少刷知乎多做题