二叉树的垂直遍历

难度: Medium

Submission

运行时间: 23 ms

内存: 16.1 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 verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        pos = defaultdict(list)
        if not root:
            return []
        
        stack = collections.deque([(root, 0)])
        while stack:
            p, index = stack.popleft()
            pos[index].append(p.val)
            if p.left:
                stack.append((p.left, index-1))
            if p.right:
                stack.append((p.right, index+1))

        index = [k for k in pos.keys()]
        index.sort()
        res = []

        for x in index:
            res.append(pos[x])
        
        return res

Explain

这个题解使用了BFS的思路来遍历二叉树，并用一个哈希表pos来记录每个节点的横坐标和对应的节点值。具体步骤如下： 1. 如果根节点为空，直接返回空列表。 2. 初始化一个双端队列stack，并将根节点和其横坐标0作为元组放入队列。 3. 当队列不为空时，循环执行以下操作： - 从队列左端取出一个节点p和其横坐标index。 - 将节点p的值加入哈希表pos中，键为index，值为一个列表，存储所有横坐标为index的节点值。 - 如果p的左子节点存在，将其与横坐标index-1作为元组放入队列。 - 如果p的右子节点存在，将其与横坐标index+1作为元组放入队列。 4. 遍历完成后，将哈希表pos的所有键（即横坐标）排序。 5. 按照排序后的横坐标顺序，将对应的节点值列表依次加入结果列表res中。 6. 返回结果列表res。

时间复杂度: O(n + klogk)，最坏情况下为O(nlogn)

空间复杂度: O(n)

```python
# 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 verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        pos = defaultdict(list)  # 创建一个默认值为空列表的哈希表，用于存储节点的横坐标和对应的节点值
        if not root:
            return []  # 如果根节点为空，直接返回空列表
        
        stack = collections.deque([(root, 0)])  # 初始化一个双端队列，并将根节点和其横坐标0作为元组放入队列
        while stack:
            p, index = stack.popleft()  # 从队列左端取出一个节点p和其横坐标index
            pos[index].append(p.val)  # 将节点p的值加入哈希表pos中，键为index，值为一个列表，存储所有横坐标为index的节点值
            if p.left:
                stack.append((p.left, index-1))  # 如果p的左子节点存在，将其与横坐标index-1作为元组放入队列
            if p.right:
                stack.append((p.right, index+1))  # 如果p的右子节点存在，将其与横坐标index+1作为元组放入队列

        index = [k for k in pos.keys()]  # 获取哈希表pos的所有键（即横坐标）
        index.sort()  # 对横坐标进行排序
        res = []  # 初始化结果列表

        for x in index:  # 按照排序后的横坐标顺序遍历
            res.append(pos[x])  # 将对应的节点值列表加入结果列表
        
        return res  # 返回结果列表
```

Explore

在进行二叉树的垂直遍历时，选择广度优先搜索（BFS）主要是为了确保节点值按照从上到下的顺序被处理和收集。使用BFS可以保证一层层地遍历树节点，这样在同一垂直线上的节点，上层的总是先于下层被访问和记录，从而满足题目对顺序的要求。相比之下，深度优先搜索（DFS）可能会首先访问较深的节点，这就需要额外的逻辑来调整顺序，增加了实现的复杂度。

在此题解中，哈希表的键是节点的横坐标，而值是一个列表，这个列表按照节点被访问的顺序存储节点值。当两个节点具有相同的横坐标但位于不同的深度时，由于使用了BFS，较浅的节点会先于较深的节点被访问和加入到列表中。因此，在最终结果中，同一垂直线上的节点会按照从上到下的顺序出现，即使它们的深度不同。

在使用广度优先搜索遍历时，我们通过维护一个队列来控制节点的访问顺序。初始时，根节点被加入队列。在遍历过程中，每次从队列中取出一个节点，按照从左到右的顺序依次将其子节点加入队列。这样，队列始终按照从上到下，从左到右的顺序保持节点。每个节点的值被按照它们被访问的顺序加入到对应横坐标的列表中，从而保证了最终输出的垂直列表中节点值是从上到下的。

在代码中使用defaultdict(list)作为pos的数据结构带来了几个好处：首先，它允许直接添加元素到任何未初始化的键中，这样当我们尝试向一个新的横坐标键中添加节点值时，不需要首先检查这个键是否已经存在于字典中；其次，这种结构简化了代码的编写，提高了代码的可读性和效率。例如，直接使用pos[index].append(p.val)即可添加元素，无需额外的初始化步骤。