LeetCode 1424对角线遍历 II | 前缀和分组引言对角线遍历 IIDiagonal Traverse II是 LeetCode 第 1424 题难度为 Medium。题目要求按照对角线顺序遍历一个二叉树数组返回所有对角线上的节点值。这道题展示了前缀和对角线索引在排序和分组中的应用。对角线遍历的特点是同一条对角线上的所有元素具有相同的行索引与列索引之差或者行索引与列索引之和取决于定义。利用这个性质我们可以将同一条对角线的元素分组然后按顺序输出。问题分析题目描述给定一个二叉树数组 nums其中每个元素是一个列表包含树的节点值。返回对角线遍历的结果其中对角线定义为所有具有相同 (row col) 值的元素。例如输入 nums [[1,2,3],[4,5,6],[7,8,9]]按照对角线遍历的顺序返回 [1,4,2,7,5,3,8,6,9]。对角线的性质在二维数组中对角线上的所有元素满足 row - col 常数 或 row col 常数。如果使用 row col 常数则对角线 0只有 (0, 0)对角线 1(0, 1), (1, 0)对角线 2(0, 2), (1, 1), (2, 0)以此类推同一对角线上的元素按照它们在原始数组中的顺序应该按 row 升序或按 col 降序排列。解决方案哈希表分组def findDiagonalOrder(nums): diagonal_map {} for i, row in enumerate(nums): for j, val in enumerate(row): if i j not in diagonal_map: diagonal_map[i j] [] diagonal_map[i j].append(val) result [] for d in range(len(diagonal_map)): result.extend(reversed(diagonal_map[d])) return result这个方法使用哈希表存储每条对角线的元素。键是 i j对角线索引值是该对角线上的元素列表。然后按对角线索引顺序输出记得反转顺序使得 row 升序。算法详解为什么需要反转在将元素添加到对角线列表时我们按照 row 升序遍历。当按行遍历时对于同一对角线上的元素较小的 row 会先被添加所以列表中的顺序是 row 升序。但是对角线遍历要求较小的 row 在后面因为对角线是从右上到左下的方向。例如对角线 2 有元素 (0, 2), (1, 1), (2, 0)按 row 升序遍历时顺序是 0, 2 - 1, 1 - 2, 0但我们需要输出 2, 0 - 1, 1 - 0, 2即 row 降序。所以需要反转列表。另一种理解当我们按 i j d 收集元素时j 较大的元素先被添加因为 j d - ii 较小时 j 较大所以列表顺序是 j 降序。反转后变成 j 升序即 row 升序。复杂度分析时间复杂度时间复杂度为 O(n)其中 n 是所有元素的总和。每个元素被处理一次添加到哈希表一次从哈希表取出一次。空间复杂度空间复杂度为 O(n)用于存储哈希表和结果数组。代码实现Python 实现def findDiagonalOrder(nums): diagonal_map {} for i, row in enumerate(nums): for j, val in enumerate(row): if i j not in diagonal_map: diagonal_map[i j] [] diagonal_map[i j].append(val) result [] for d in range(len(diagonal_map)): result.extend(reversed(diagonal_map[d])) return resultJava 实现public int[] findDiagonalOrder(ListListInteger nums) { MapInteger, ListInteger diagonalMap new LinkedHashMap(); for (int i 0; i nums.size(); i) { for (int j 0; j nums.get(i).size(); j) { int key i j; diagonalMap.putIfAbsent(key, new ArrayList()); diagonalMap.get(key).add(nums.get(i).get(j)); } } ListInteger result new ArrayList(); int d 0; while (diagonalMap.containsKey(d)) { ListInteger diagonal diagonalMap.get(d); for (int i diagonal.size() - 1; i 0; i--) { result.add(diagonal.get(i)); } d; } return result.stream().mapToInt(Integer::intValue).toArray(); }边界情况处理空数组当 nums 为空时应该返回空结果。代码会正确处理因为外层循环不会执行。只有一个元素当只有一个元素时如 [[5]]对角线索引为 0 的列表包含 [5]反转后仍然是 [5]。每行元素数量不同代码正确处理了每行元素数量不同的情况因为内层循环遍历每行的实际元素。单行数组当只有一行时如 [[1, 2, 3]]每条对角线只有一个元素输出顺序就是 [1, 2, 3]。测试用例def test_find_diagonal_order(): assert findDiagonalOrder([[1,2,3],[4,5,6],[7,8,9]]) [1,4,2,7,5,3,8,6,9] assert findDiagonalOrder([[1,2,3],[4,5,6]]) [1,4,2,5,3] assert findDiagonalOrder([[1],[2],[3]]) [1,2,3] assert findDiagonalOrder([[1]]) [1] assert findDiagonalOrder([]) [] assert findDiagonalOrder([[1,2,3,4,5]]) [1,2,3,4,5] print(所有测试用例通过)扩展问题使用 Counter可以使用 collections.Counter 来代替手动创建哈希表from collections import defaultdict def findDiagonalOrder_counter(nums): diagonal defaultdict(list) for i, row in enumerate(nums): for j, val in enumerate(row): diagonal[i j].append(val) result [] for d in sorted(diagonal.keys()): result.extend(reversed(diagonal[d])) return result返回对角线的起始位置如果题目要求返回每个对角线的起始位置或统计信息可以修改代码收集额外信息。总结对角线遍历 II 问题展示了前缀和对角线索引在分组和排序中的应用。通过使用 i j 作为键我们将同一条对角线的元素分组然后反转顺序输出。这个问题虽然不直接涉及区间求和但它利用了前缀和的差值相同性质来识别同一条对角线。希望通过本文的讲解读者能够理解前缀和概念的更广泛应用并将其推广到更多类似问题的解决中。
