企业官网建设流程全解析

LeetCode 1424：对角线遍历 II | 前缀和分组

引言

对角线遍历 II（Diagonal 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 - i，i 较小时 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 result

Java 实现

public int[] findDiagonalOrder(List<List<Integer>> nums) { Map<Integer, List<Integer>> 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)); } } List<Integer> result = new ArrayList<>(); int d = 0; while (diagonalMap.containsKey(d)) { List<Integer> 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 作为键，我们将同一条对角线的元素分组，然后反转顺序输出。

这个问题虽然不直接涉及区间求和，但它利用了前缀和的"差值相同"性质来识别同一条对角线。希望通过本文的讲解，读者能够理解前缀和概念的更广泛应用，并将其推广到更多类似问题的解决中。