题目描述

思路

• 垂直方向按 level 划分，root的level为0，往左 自减1 往右自增 1

• BFS 会按从上到下的顺序记录下 垂直方向的顺序，然后再用一个字典存储 垂直方向的数据即可（在遍历时垂直方向已经有序）

• DFS 在遍历时并不能保证垂直方向是有序的，可以额外加一个字段，用来标记遍历的数据的层数。（ - 那为啥不直接用BFS层序遍历？ - 因为我想练习DFS -_-# ）

• BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def verticalOrder(self, root: TreeNode) -> List[List[int]]:if not root: return []queue = collections.deque()data = collections.defaultdict(list)queue.append((root, 0))while queue:top, level = queue.popleft()data[level].append(top.val)if top.left:queue.append((top.left, level-1))if top.right:queue.append((top.right, level+1))return [_[1] for _ in sorted(data.items(), key=lambda item: item[0])]

• DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def verticalOrder(self, root: TreeNode) -> List[List[int]]:if not root: return []def dfs(node, num, deep):if node:data[num].append([node.val, deep])# else: returnif node.left:deep += 1dfs(node.left, num-1, deep)deep -= 1  # 回溯if node.right:deep += 1dfs(node.right, num+1, deep)deep -= 1  # 回溯passdata = collections.defaultdict(list)dfs(root, 0, 0)mid =  [_[1] for _ in sorted(data.items(), key=lambda a: a[0])]res = []for one in mid:res.append([_[0] for _ in sorted(one, key=lambda ele:ele[1])])return res

• Time : $O(n)$ ，即将二叉树遍历一遍，n是e二叉树节点个数
• Space : $O(n)$