二叉树的垂序遍历

难度: Hard

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

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

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

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

示例 1：

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

示例 2：

输入：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：

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

提示：

树中结点数目总数在范围 [1, 1000] 内
0 <= Node.val <= 1000

Submission

运行时间: 16 ms

内存: 16.3 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        nodes = list()

        def dfs(node: TreeNode, row: int, col: int) -> None:
            if not node:
                return

            nodes.append((col, row, node.val))
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)
        nodes.sort()
        ans, lastcol = list(), float("-inf")

        for col, row, value in nodes:
            if col != lastcol:
                lastcol = col
                ans.append(list())
            ans[-1].append(value)
        
        return ans

Explain

本题解使用深度优先搜索（DFS）遍历二叉树，将每个节点的列、行、值信息存储到一个列表中。然后对列表进行排序，按照列、行、值的顺序进行排序。最后遍历排序后的列表，将相同列的节点值放入同一个子列表中，最终得到按垂序遍历顺序排列的结果列表。

时间复杂度: O(nlogn)

空间复杂度: O(n + w)

class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        nodes = list()

        def dfs(node: TreeNode, row: int, col: int) -> None:
            if not node:
                return

            # 将节点的列、行、值信息存储到列表中
            nodes.append((col, row, node.val))
            # 递归遍历左子树，列减 1，行加 1
            dfs(node.left, row + 1, col - 1)
            # 递归遍历右子树，列加 1，行加 1
            dfs(node.right, row + 1, col + 1)

        # 执行 DFS 遍历
        dfs(root, 0, 0)
        # 对存储节点信息的列表进行排序
        nodes.sort()
        ans, lastcol = list(), float("-inf")

        # 遍历排序后的列表，生成结果列表
        for col, row, value in nodes:
            if col != lastcol:
                lastcol = col
                ans.append(list())
            ans[-1].append(value)
        
        return ans

Explore

在DFS过程中，每次递归调用时，都会根据当前节点的位置（列col和行row）以及是左子树还是右子树来调整新的列和行的值。对于左子节点，列值会减1（col - 1），行值会加1（row + 1）；对于右子节点，列值会加1（col + 1），行值同样加1（row + 1）。这样的递归调整确保了每个节点根据其在二叉树中的位置被正确地归类到相应的列和行。

排序的目的是为了按照题目要求的垂序遍历输出顺序组织节点。首先按列排序是因为垂序遍历首先需要按列分组。其次，在同一列内，节点按行排序，这是因为在同一列中，更高的行（更深的节点）应该在输出中排在更低的行之后。最后，在相同的列和行中，按节点的值进行排序，确保在输出中值较小的节点先显示。这种排序顺序确保了最终的输出列表能够正确反映垂序遍历的顺序。

是的，直接使用`nodes.sort()`对元组列表进行排序时，Python默认按元组中的元素顺序进行升序排序。因为元组中的第一个元素是列号，第二个是行号，第三个是节点值，所以在同一列和行的情况下，节点值作为第三排序关键字，确保了同列同行的节点按值升序排列。

在遍历排序后的列表时，使用了变量`lastcol`来跟踪上一个处理的列号。遍历时，若当前节点的列号与`lastcol`不同，这表示已经达到一个新的列，因此会开始一个新的子列表，并更新`lastcol`为当前列号。若列号相同，则继续在当前的子列表中添加节点值。这样可以确保不同列的节点被正确地分组到不同的子列表中。