给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例1

1
2
3
4
5
6
7
输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列  1 ：只有结点 20 在此列中。
列  2 ：只有结点 7 在此列中。

示例2

1
2
3
4
5
6
7
8
9
10
输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列  0 ：结点 1 、5 和 6 都在此列中。
          1 在上面，所以它出现在前面。
          5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列  1 ：只有结点 3 在此列中。
列  2 ：只有结点 7 在此列中

示例3

1
2
3
4
5
输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

实际上每一个顶点都是一个三元组(col,row,val),我们要将具有相同的col的节点归为一类，然后对col排序，然后在每一类里面再根据val排序。我们用一个以列表为默认值的defaultdict接受值，以col为字典的键。接受所有值后，对字典按键排序，在输出正确结果前，再对字典里每一个键对应的列表里的所有元组先按row排序，row相同的再按val排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        groups = defaultdict(list)
        def dfs(root,col,row):
            if root is None:
                return
            groups[col].append((row,root.val))#每一个列号下添加每一行中该列元素的元组
            dfs(root.left,col-1,row+1)
            dfs(root.right,col+1,row+1)
        dfs(root,0,0)
        ans = []
        for _,g in sorted(groups.items()):
            g.sort()
            ans.append([val for _,val in g])
        return ans
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。