对角线遍历

https://www.lintcode.com/problem/1205/description?utm_source=sc-libao-ql

描述

给定M×N个元素的矩阵（M行，N列），以对角线顺序返回矩阵的所有元素，如下例所示。

给定矩阵的元素总数不会超过10,000。

样例

例1:

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

例2:

输入:[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]输出:[1,2,5,9,6,3,4,7,10,13,14,11,8,12,15,16]

解题思路：

规律：对角线上的坐标和相等， 比如第三条对角线上，所有元素的坐标和都是3: (3,0),(1,2),(2,1),(0,3), 遍历Matrix，
以坐标和为key，该对角线上所有元素的集合List为value, 建立一个dict
最后dict里, 复数坐标list直接存入，单数翻转存入结果

```python
from typing import (
    List,
)

class Solution:
    """
    @param matrix: a 2D array
    @return: return a list of integers
    """
    def find_diagonal_order(self, matrix: List[List[int]]) -> List[int]:
        # write your code here
        list翻转存入结果
        res = []
        if not matrix:
            return res
        d = collections.defaultdict(list)
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                d[i + j + 1].append(matrix[i][j])
        
        for k,v in d.items():
            if k%2 != 0:
                v.reverse()
            res += v
        return res


```