题目关键词，从左到右，从上到下，那么使用bfs宽度优先算法。

使用字典v保存每一列的值。

class Solution:def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root: return []v = defaultdict(list)qu = deque()qu.append([root, 0])while qu:node, column = qu.popleft()v[column].append(node.val)if node.left: qu.append([node.left, column - 1])if node.right: qu.append([node.right, column + 1])return [ v[x] for x in sorted(v.keys())]

刚开始我使用的还是dfs，发现过程确实复杂一些，不能从上到下遍历。这是我原来的代码：

class Solution:def __init__(self):self.ans = defaultdict(dict)self.idx = 0def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root: return []self.init_idx(root, 0)self.dfs(root, -self.idx, 0)ans = []k1 = sorted(self.ans.keys())for x in k1:ans.append([])k2 = sorted(self.ans[x].keys())for y in k2:ans[-1] += self.ans[x][y]return ansdef init_idx(self, root, idx):if root.left:self.init_idx(root.left, idx - 1)if root.right:self.init_idx(root.right, idx + 1)self.idx = min(self.idx, idx)def dfs(self, root, idx, idy):if not root: returnif idy not in self.ans[idx]:self.ans[idx][idy] = [root.val]else:self.ans[idx][idy].append(root.val)self.dfs(root.left, idx-1, idy + 1)self.dfs(root.right, idx+1, idy + 1)

 

 回顾一下，发现init_idx这个函数没必要，他目的是，如果中间节点root的列的编号为0，那么最左边节点的列的编号为self.idx，可以推出，如果最左边节点列的编号为0，那么root排在第-self.idx列。

可以省掉这一步，直接设置root节点为第0列，左节点为-1列，右节点为第1列，最后在把列排个序。这样的话，左节点-1直接变道0，root变道1，右节点变道2.