寻求二维数组对角线遍历的通用BFS解法及公式推导提示

Hey, let's break this down for you. You're totally right to avoid that messy conditional-heavy solution—leaning into the diagonal's core mathematical property is the key to a cleaner, more general approach. Let's first figure out why your BFS code is looping, then walk through better ways to solve this problem.

Why Your Current BFS Is Stuck #

Your code is getting stuck in a loop because of a few critical issues:

• Invalid Node Generation: When you create the level list, you're not checking if the generated coordinates ((step-i, i) or (i, step-i)) are actually within the matrix bounds. This leads to adding nodes that don't exist, but your loop doesn't account for this, so it keeps processing invalid entries.
• Confused Step Logic: Your handling of step and how you populate the queue is inconsistent. For example, after processing the first node (0,0), you manually add (0,1) but then try to generate a full level based on step, leading to duplicate or incorrect nodes being added.
• No Visited Tracking: BFS can end up adding the same node multiple times from different paths (e.g., (1,1) can be reached from (0,1) or (1,0)), but you don't track visited nodes, so the queue keeps growing with duplicates.

The Core Property to Leverage #

The big insight here is that every node on the same diagonal has the same sum of its row and column indices (let's call this sum s = r + c). For your example matrix:

• s=0: (0,0) → value 1
• s=1: (0,1), (1,0) → values 2,4
• s=2: (2,0), (1,1), (0,2) → values7,5,3
• And so on.

Additionally, the traversal direction alternates with each s:

• When s is even: we traverse the diagonal from bottom to top (so we start with the largest valid row index for that s)
• When s is odd: we traverse from top to bottom (start with the smallest valid row index for that s)

Clean General Solution (No BFS, Just Diagonal Traversal) #

This is the most efficient and readable approach, leveraging the s property directly. No messy conditionals, just straightforward iteration over each diagonal:

from typing import List

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
        
        rows, cols = len(matrix), len(matrix[0])
        result = []
        
        # Iterate over all possible diagonal sums (from 0 to (rows-1)+(cols-1))
        for s in range(rows + cols - 1):
            if s % 2 == 0:
                # Even sum: traverse from bottom to top
                # Start at the maximum valid row for this sum, end at the minimum valid row
                start_r = min(s, rows - 1)
                end_r = max(0, s - cols + 1)
                for r in range(start_r, end_r - 1, -1):
                    c = s - r
                    result.append(matrix[r][c])
            else:
                # Odd sum: traverse from top to bottom
                # Start at the minimum valid row for this sum, end at the maximum valid row
                start_r = max(0, s - cols + 1)
                end_r = min(s, rows - 1)
                for r in range(start_r, end_r + 1):
                    c = s - r
                    result.append(matrix[r][c])
        
        return result

This works for any M×N matrix, and the logic is easy to follow—we just calculate the valid range of rows for each diagonal sum s, then iterate in the correct direction.

Fixed BFS Approach #

If you really want to use BFS (maybe for practice with traversal techniques), here's how to adapt it to use the diagonal sum property. We'll track each level (diagonal) and reverse the order when needed:

from typing import List
from collections import deque

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
        
        rows, cols = len(matrix), len(matrix[0])
        result = []
        queue = deque()
        visited = set()
        
        # Start with the top-left corner
        queue.append((0, 0))
        visited.add((0, 0))
        
        while queue:
            level_size = len(queue)
            current_level = []
            
            for _ in range(level_size):
                r, c = queue.popleft()
                current_level.append(matrix[r][c])
                
                # Add the two possible next nodes (down and right) if valid
                for nr, nc in [(r + 1, c), (r, c + 1)]:
                    if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited:
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            
            # Determine the direction based on the diagonal sum (all nodes in level have same s)
            s = r + c
            if s % 2 == 0:
                # Even sum: reverse the level to get bottom-to-top order
                result.extend(reversed(current_level))
            else:
                # Odd sum: keep top-to-bottom order
                result.extend(current_level)
        
        return result

This BFS works by processing each diagonal as a level. Since BFS naturally collects nodes in top-to-bottom order for each diagonal, we just reverse the level when the sum s is even to match the problem's required traversal order.

Wrap-Up #

The key takeaway here is leaning into the mathematical property of diagonals (r + c = s)—it simplifies the problem drastically and leads to a general solution that works for any matrix size. Your initial BFS idea was solid, but it needed better handling of level generation, boundary checks, and visited tracking.

内容的提问来源于stack exchange，提问作者Alice