学过二叉树的人都了解 前序遍历、中序遍历、后序遍历，层次遍历，但是垂序遍历是什么呢？你可以想象一条竖直的直线（这里设定直线没有终点），直线开始在二叉树的最左边，慢慢将直线从最左边平移到最右边，先接触到的节点排在前面，（如果两个节点同时碰到的话，如果节点值更小，则将节点排在前面）
  下面以一个算法来了解它。

二叉树的垂序遍历

给定二叉树，按垂序遍历返回其结点值。

对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。

把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。

如果两个结点位置相同，则首先报告的结点值较小。

按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表

例子

使用DFS

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

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        mapping = defaultdict(list)             #构建一个字典，用来储存每一个节点的，位置，深度、值的信息。

        def dfs(root, x, y):
            if not root:
                return
            
            dfs(root.left, x-1, y-1)            #先遍历左边
            mapping[x].append((-y,root.val))    #遍历根
            dfs(root.right, x+1, y-1)           #再遍历右边
        
        dfs(root, 0, 0)                         #调用dfs函数
        keys = sorted(list(mapping.keys()))     #对位置信息进行排序，（从小到大）
        
        # res=[]
        # for k in keys:
        #     newlist=sorted(mapping[k])
        #     for i in newlist:
        #         res.append(i[1])
        # return res
        
        #首先对位置进行遍历， 然后对在每一个位置的值进行排序，
        #下面进行简化到一行。
        return [[ i[1] for i in sorted(mapping[k])] for k in keys]  

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree