314. Binary Tree Vertical Order Traversal(树bfs）

bfs dfs

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be fromleft to right.

Example

Given binary tree{3,9,20,#,#,15,7}

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7

Return its vertical order traversal as: [[9],[3,15],[20],[7]]

Given binary tree{3,9,8,4,0,1,7}

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7

Return its vertical order traversal as: [[4],[9],[3,0,1],[8],[7]]

分析

如果是要求层顺序，使用bfs，如果要求root和l,r顺序，考虑pre in post

这题不知道为什么dfs不行，可能因为顺序？

因为要求行列都顺序，BFS天然保留了行顺序，只需要考虑COL顺序

但DFS需要加入额外的ROW追踪。

DFS

from collections import defaultdict

class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        # Dictionary to store nodes by column and row
        column_map = defaultdict(list)
        min_col = max_col = 0
        
        def dfs(node, row, col):
            nonlocal min_col, max_col
            if not node:
                return
            
            column_map[col].append((row, node.val))
            min_col = min(min_col, col)
            max_col = max(max_col, col)
            
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)
        
        dfs(root, 0, 0)
        
        # Sort each column's entries by row, then by insertion order
        result = []
        for col in range(min_col, max_col + 1):
            # Sort by row to maintain top-to-bottom order
            column_map[col].sort(key=lambda x: x[0])
            # Extract just the values
            result.append([val for (row, val) in column_map[col]])
        
        return result

coldict可以用负数做Key和排序, 必须追踪ROW， 因为row也需要排序输出， 如果没有row #， 无法给行排序。

 # 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
from collections import deque


class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        q = deque([(root, 0,0)])
        cols = collections.defaultdict(list)
        while q:
            node, row, col = q.popleft()
            cols[col].append((row,node.val))
            if node.left:
                q.append((node.left, row+1, col-1))
            if node.right:
                q.append((node.right, row+1, col+1))
        res = []
        for col in sorted(cols.keys()):
            cols[col].sort()
            res.append([v for r,v in cols[col]])
        return res