文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
**解析：**Version 1，根据矩阵对角线元素的规律，行坐标与列坐标和相等的元素属于同一对角线，由于对角线从左下到右上，因此应该同一对角线的元素应该按列坐标的顺序排列，将所有元素按(i+j, j, nums[i][j])保存，并按照(i+j,j)进行排序即可。Version 2，每一条对角线上的数据保存到一个列表中，列表的索引为行坐标与列坐标的和，由于每一条对角线的元素是按照行顺序保存的，因此合并时应将顺序反转。Version 3把问题看做是一个树的遍历问题(广度优先搜索)，每个节点只关心其下边的点及其右侧的点，下边的点只有第一行才有，右侧的点每个点都有，否则会出现重复搜索，要对点是否存在进行判断，搜索顺序使用队列实现。
- Version 1
class Solution:def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:diagonals = []for i in range(len(nums)):for j in range(len(nums[i])):diagonals.append((i+j, j, nums[i][j]))diagonals.sort(key=lambda x: (x[0], x[1]))result = [x[2] for x in diagonals]return result
- Version 2
class Solution:def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:diagonals = []for i in range(len(nums)):for j in range(len(nums[i])):if i + j == len(diagonals):diagonals.append([])diagonals[i+j].append(nums[i][j])result = []for diagonal in diagonals:result += diagonal[::-1]return result
- Version 3
class Solution:def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]: result = []queue = collections.deque([(0, 0)])while queue:i, j = queue.popleft()result.append(nums[i][j])if i < len(nums) - 1 and j == 0:queue.append((i+1, j))if j < len(nums[i]) - 1:queue.append((i, j+1))return result
Reference
- https://leetcode.com/problems/diagonal-traverse-ii/