递归实现Zigzag遍历二维数组时遇IndexError问题求助

错误原因分析 #

你的代码终止条件判断有误：当前仅当row > last_row且col > last_col时才返回，但实际只要其中一个索引超出数组范围（比如row已经超过最后一行，但col仍在有效范围内，反之亦然），就会触发IndexError。比如遍历到最后一个元素(last_row, last_col)后，下一步计算出的row或col会超出边界，此时进入递归函数会先执行num = array[row][col]，而此时还未触发终止条件，导致访问无效索引。

修正方案 #

在函数开头先判断索引是否越界，只要row超出有效范围（row < 0或row > last_row），或者col超出有效范围（col < 0或col > last_col），就直接返回，避免后续的数组访问操作。

修正后的代码 #

# Time: O(n) | # Space: O(n)
def zigzagTraverse_recursion(array):
    zigzag_traverse = []
    zigzag(0, 0, True, array, zigzag_traverse)
    return zigzag_traverse

def zigzag(row, col, down, array, zigzag_traverse):
    last_row = len(array) - 1
    last_col = len(array[0]) - 1
    # 先判断索引是否越界，越界直接返回
    if row < 0 or row > last_row or col < 0 or col > last_col:
        return

    num = array[row][col]
    zigzag_traverse.append(num)

    # 如果已经遍历到最后一个元素，无需继续递归
    if row == last_row and col == last_col:
        return

    if down:
        if row == last_row:
            down = False
            col += 1
        elif col == 0:
            down = False
            row += 1
        else:
            row += 1
            col -= 1
    else:
        if col == last_col:
            down = True
            row += 1
        elif row == 0:
            down = True
            col += 1
        else:
            row -= 1
            col += 1

    zigzag(row, col, down, array, zigzag_traverse)

补充说明 #

• 新增的越界判断放在函数最开头，确保任何无效索引都不会触发数组访问。
• 额外添加了row == last_row and col == last_col的判断，遍历到最后一个元素后直接返回，避免不必要的递归调用。

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