leetcode-498：对角线遍历

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出:  [1,2,4,7,5,3,6,8,9]

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        # Check for empty matrices
        if not matrix or not matrix[0]:
            return []
        # Variables to track the size of the matrix
        N, M = len(matrix), len(matrix[0])
        # The two arrays as explained in the algorithm
        result, intermediate = [], []
        # We have to go over all the elements in the first
        # row and the last column to cover all possible diagonals
        for d in range(N + M - 1):
            # Clear the intermediate array everytime we start
            # to process another diagonal
            intermediate.clear()
            # We need to figure out the "head" of this diagonal
            # The elements in the first row and the last column
            # are the respective heads.
            r, c = 0 if d < M else d - M + 1, d if d < M else M - 1
            # Iterate until one of the indices goes out of scope
            # Take note of the index math to go down the diagonal
            while r < N and c > -1:
                intermediate.append(matrix[r][c])
                r += 1
                c -= 1
            # Reverse even numbered diagonals. The
            # article says we have to reverse odd 
            # numbered articles but here, the numbering
            # is starting from 0 :P
            if d % 2 == 0:
                result.extend(intermediate[::-1])
            else:
                result.extend(intermediate)
        return result