1766-互质树

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的
根节点 为 0 号点。

给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值，edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。

当 gcd(x, y) == 1 ，我们称两个数 x 和 y 是 互质的 ，其中 gcd(x, y) 是 x 和 y 的
最大公约数 。

从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。

请你返回一个大小为 n 的数组 ans ，其中 __ans[i]是离节点 i 最近的祖先节点且满足 __nums[i] 和
__nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，ans[i] 为 -1 。

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2021/02/20/untitled-diagram.png)

**输入：** nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
**输出：** [-1,0,0,1]
**解释：** 上图中，每个节点的值在括号中表示。
- 节点 0 没有互质祖先。
- 节点 1 只有一个祖先节点 0 。它们的值是互质的（gcd(2,3) == 1）。
- 节点 2 有两个祖先节点，分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的（gcd(3,3) == 3）但节点 0 的值是互质的(gcd(2,3) == 1)，所以节点 0 是最近的符合要求的祖先节点。
- 节点 3 有两个祖先节点，分别是节点 1 和节点 0 。它与节点 1 互质（gcd(3,2) == 1），所以节点 1 是离它最近的符合要求的祖先节点。

示例 2：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2021/02/20/untitled-diagram1.png)

**输入：** nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
**输出：** [-1,0,-1,0,0,0,-1]

提示：

  • nums.length == n
  • 1 <= nums[i] <= 50
  • 1 <= n <= 105
  • edges.length == n - 1
  • edges[j].length == 2
  • 0 <= uj, vj < n
  • uj != vj

【大致过程】

  1. 题目给的节点数量很大，但取值范围很小，只有[1,50]。那就先把[1,50]中，每个数值有多少互质数，以及分别是哪些互质数，都列出来。
    如下面代码中所提，gPrimeSize[num]表示数值num一共有多少个互质数。gPrime[num][i]表示数值num的第i个互质数。
  2. 定义几个数组。
    counter[51]: 其中counter[num]表示数值num在树中出现的总数。初始化为全0。·
    layer[n]: 其中layer[x]表示节点x在树中的层级。除了根节点0是一开始就明确在第0层（即layer[0] == 0）之外，其它的节点一开始在第几层并不明确。先初始化为无效值-1。
    children[n]: 其中children[x]表示节点x的子节点列表，这里用链表格式。初始化都是NULL，即空链表。
  3. 遍历edges[]数组，先生成各个节点的子节点列表children[]。
    一开始时，除了明确知道节点0是根节点以外，其余的节点并不知道谁是父节点，谁是子节点。即edges[x][0]和edges[x][1]，并不知道谁在上谁在下。这时候先不着急，把它们先互视为对方的子节点，下面再说。
  4. 开始生成树。从已知是根节点的0开始，借助队列queue，执行层序遍历。
    即节点0先入队，然后逐个从队首出队节点，出队节点的同时，把它的子节点列表入队尾，如此循环，直到叶子节点为止。
    生成树的同时，就顺便计算了counter[]和layer[]两个数组。
  5. 根据counter[]数值，给[1,50]每个数值生成一个大小合适的栈空间，方便下面递归计算时出入栈使用。
  6. 从根节点0开始进行递归计算。
    每递归计算到某个节点x时，查看其数值nums[x]的所有互质数，在每一个互质数中，查看对应的栈是否为空，如果不为空，则栈顶的节点xTop，对应的层数layer[xTop]，哪一个离自己最近，那么，所要求的结果就是这个xTop。如果所有的互质数对应的栈都是空的，那就是题目要求的-1。

PIC_20230629110552.png{:width=400}

【代码】
时间复杂度，O(n*E)，空间复杂度O(n + E^2)，其中n表示输入的节点数量，E表示取值范围[1,50]。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
/* 简要说明。
  1. 先生成树，其中0为根节点。
  2. 获得各个节点所处的层级。
  3. 从根节点往下进行递归运算，每个节点往上查询所有的互质数，层级离自己最近的。
  4. 往下递归调用子节点时，把自己的节点入栈。
  5. 调用完子节点之后，自己的节点出栈。 */

#define MOST_NUM            51
#define MAX_VALUE(x, y)     ((x) > (y) ? (x) : (y))

/* 事先把[0,50]范围内，每个数值有多少个互质数，以及分别是哪些互质数都列出来，减少后面的计算时间。 */
static const int gPrimeSize[MOST_NUM] = {0,50,25,34,25,40,17,43,25,34,20,46,17,47,21,27,25,48,17,48,20,29,23,48,17,40,23,34,21,49,14,49,25,31,24,34,17,49,24,32,20,49,14,49,23,27,24,49,17,43,20};
static const int gPrime[MOST_NUM][MOST_NUM] = { {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,0},
                {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41,43,44,46,47,49,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49,0,0,0,0,0,0,0,0,0,0,0},
                {1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,8,9,10,11,12,13,15,16,17,18,19,20,22,23,24,25,26,27,29,30,31,32,33,34,36,37,38,39,40,41,43,44,45,46,47,48,50,0,0,0,0,0,0,0,0},
                {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41,43,44,46,47,49,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,12,13,14,15,16,17,18,19,20,21,23,24,25,26,27,28,29,30,31,32,34,35,36,37,38,39,40,41,42,43,45,46,47,48,49,50,0,0,0,0,0},
                {1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,21,22,23,24,25,27,28,29,30,31,32,33,34,35,36,37,38,40,41,42,43,44,45,46,47,48,49,50,0,0,0,0},
                {1,3,5,9,11,13,15,17,19,23,25,27,29,31,33,37,39,41,43,45,47,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,7,8,11,13,14,16,17,19,22,23,26,28,29,31,32,34,37,38,41,43,44,46,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,0,0,0},
                {1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,39,40,41,42,43,44,45,46,47,48,49,50,0,0,0},
                {1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,5,8,10,11,13,16,17,19,20,22,23,25,26,29,31,32,34,37,38,40,41,43,44,46,47,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,5,7,9,13,15,17,19,21,23,25,27,29,31,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,47,48,49,50,0,0,0},
                {1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,5,7,9,11,15,17,19,21,23,25,27,29,31,33,35,37,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41,43,44,46,47,49,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,5,9,11,13,15,17,19,23,25,27,29,31,33,37,39,41,43,45,47,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,0,0},
                {1,7,11,13,17,19,23,29,31,37,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,0,0},
                {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32,34,35,37,38,40,41,43,46,47,49,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,5,7,9,11,13,15,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34,36,37,38,39,41,43,44,46,47,48,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,38,39,40,41,42,43,44,45,46,47,48,49,50,0,0},
                {1,3,5,7,9,11,13,15,17,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,5,7,8,10,11,14,16,17,19,20,22,23,25,28,29,31,32,34,35,37,38,40,41,43,44,46,47,49,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,42,43,44,45,46,47,48,49,50,0,0},
                {1,5,11,13,17,19,23,25,29,31,37,41,43,47,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,44,45,46,47,48,49,50,0,0},
                {1,3,5,7,9,13,15,17,19,21,23,25,27,29,31,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,4,7,8,11,13,14,16,17,19,22,23,26,28,29,31,32,34,37,38,41,43,44,46,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,3,5,7,9,11,13,15,17,19,21,25,27,29,31,33,35,37,39,41,43,45,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,48,49,50,0,0},
                {1,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                {1,2,3,4,5,6,8,9,10,11,12,13,15,16,17,18,19,20,22,23,24,25,26,27,29,30,31,32,33,34,36,37,38,39,40,41,43,44,45,46,47,48,50,0,0,0,0,0,0,0,0},
                {1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39,41,43,47,49,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} };

/* 链表。 */
struct LinkedNode
{
    int index;
    struct LinkedNode *next;
};

/* 双端队列。 */
struct BinodeQueue
{
    int *arr;
    int arrHead;
    int arrSize;
};

/* 栈。 */
struct SoloStack
{
    int *arr;
    int arrSize;
};

/* 队列、栈的push、pop操作，以及自定义的递归计算函数。具体实现见下。 */
static void queuePush(struct BinodeQueue *queue, int value);
static void queuePop(struct BinodeQueue *queue);
static void stackPush(struct SoloStack *stack, int value);
static void stackPop(struct SoloStack *stack);
static void recursionCalc(int *nums, int *layer, int i, struct LinkedNode **children, struct SoloStack *stack, int *result);

/* 几个局部变量说明。
  buffSize:         实际等于edgesSize * 2，表示所有节点互为父子关系，需要用到的链表节点数量。edgesSize可能是0，用1进行保护，避免用它定义数组时出错。
  x, y:             循环变量。
  layer[n]:         其中layer[x]表示节点x处在树的第几层，从0开始计，即节点0处于第0层。layer[0] == 0;
  arr[buffSize]:    队列和栈共用的数组空间。
  counter[51]:      表示各个数值的数量。counter[num]表示数值num在树中总共出现多少个。
  queue:            队列。
  node:             链表节点变量。
  buff[buffSize]:   生成每个节点的子节点列表时，用的是链表格式而非数组格式。所有的节点的子节点总数是edgesSize * 2，所以事先把总空间安排好，不用一个个malloc。
  children[]:       就是每一个节点的子节点列表，初始化都为NULL。
  stack[51]:        每个数值单独分配一个栈空间，栈空间里面存储的是节点编号。 */
int *getCoprimes(int *nums, int numsSize, int **edges, int edgesSize, int *edgesColSize, int *returnSize)
{
    const int n = numsSize, buffSize = MAX_VALUE(edgesSize << 1, 1);
    int x = 0, y = 0;
    int layer[n], arr[buffSize], counter[MOST_NUM];
    struct BinodeQueue queue;
    struct LinkedNode *node = NULL;
    struct LinkedNode buff[buffSize], *children[n];
    struct SoloStack stack[MOST_NUM];
    int *result = NULL;
    /* 初始化队列和层数数组、计数数组等。结果数组一开始全都初始化为-1。 */
    queue.arr = arr;
    queue.arrHead = 0;
    queue.arrSize = 0;
    memset(layer, -1, sizeof(layer));
    memset(counter, 0, sizeof(counter));
    memset(children, 0, sizeof(children));
    result = (int *)malloc(sizeof(int) * n);
    if(NULL == result)
    {
        *returnSize = 0;
        return result;
    }
    memset(result, -1, sizeof(int) * n);
    /* 遍历edges数组，生成树。下面过程中，buff[]数组从下标0开始逐个被使用，遍历完之后正好用完，即不用一个个malloc。
    题目给的是无向图，所以edges[x][0]和edges[x][1]一开始也分不清谁是父节点谁是子节点。除了明确节点0是根节点以外。 */
    for(x = 0; edgesSize > x; x++)
    {
        /* 把edges[x][1]加到edges[x][0]的子节点列表中。 */
        node = &buff[y];
        y++;
        node->index = edges[x][1];
        node->next = children[edges[x][0]];
        children[edges[x][0]] = node;
        /* 把edges[x][0]加到edges[x][1]的子节点列表中。 */
        node = &buff[y];
        y++;
        node->index = edges[x][0];
        node->next = children[edges[x][1]];
        children[edges[x][1]] = node;
    }
    /* 从0节点开始，记录各个数值出现数量，以及获取各个节点的层级。
    这里借助队列，进行层序遍历。layer[]除了layer[0]直接赋值为0以外，都还是初始化的无效值-1。 */
    layer[0] = 0;
    queuePush(&queue, 0);
    while(0 < queue.arrSize)
    {
        x = queue.arr[queue.arrHead];
        queuePop(&queue);
        /* 计数树中各个数值出现的次数。 */
        counter[nums[x]]++;
        /* 把它的子节点都加入队列。 */
        for(node = children[x]; NULL != node; node = node->next)
        {
            /* 不要重复把父节点加入进来，避免嵌套循环。这里就是layer[]为什么要初始化为无效值-1的原因。
            到这里为止，原来的无向图，就可以视为有向图了。因为父节点的layer[]值，比子节点的layer[]值小。 */
            if(-1 == layer[node->index])
            {
                layer[node->index] = layer[x] + 1;
                queuePush(&queue, node->index);
            }
        }
    }
    /* 给每个数值列出各自的栈空间，不可能超出这个范围。
    其实，可以给[1, 50]这50个数值，每一个安排长度为n的栈空间，这样肯定也够，但是就显得浪费了。
    这里，所有[1, 50]数值使用的栈空间，都是上面临时数组arr[]的某一段。
    上面队列queue也用的是这个arr[]数组，但队列的使命已经完成。现在要对arr[]数组进行时分复用。 */
    y = 0;
    for(x = 0; MOST_NUM > x; x++)
    {
        /* 数值x最多只需要占据counter[x]个位置，所以安排arr[]中长度counter[x]的一段即可。y值在这里表示起始位置。 */
        if(0 < counter[x])
        {
            stack[x].arr = &arr[y];
            y += counter[x];
            stack[x].arrSize = 0;
        }
        /* 从来没有出现过的数值，其栈设为空即可。后面计算过程中也不可能出现。 */
        else
        {
            stack[x].arrSize = 0;
        }
    }
    /* 开始递归计算各个节点的结果。 */
    recursionCalc(nums, layer, 0, children, stack, result);
    /* 结果数组的长度等于原数组长度。 */
    *returnSize = n;
    return result;
}

/* 队列push操作。 */
static void queuePush(struct BinodeQueue *queue, int value)
{
    queue->arr[queue->arrHead + queue->arrSize] = value;
    queue->arrSize++;
    return;
}

/* 队列pop操作。 */
static void queuePop(struct BinodeQueue *queue)
{
    queue->arrHead++;
    queue->arrSize--;
    return;
}

/* 栈顶push操作。 */
static void stackPush(struct SoloStack *stack, int value)
{
    stack->arr[stack->arrSize] = value;
    stack->arrSize++;
    return;
}

/* 栈顶pop操作。 */
static void stackPop(struct SoloStack *stack)
{
    stack->arrSize--;
    return;
}

/* 递归计算，几个入参的意义：
  nums:         主函数的数值数组，即nums[i]表示节点i的值。
  layer:        主函数传入的节点层级数组，即layer[i]表示节点i在第几层。
  i:            递归调用时，计算的各个节点编号。
  children:     主函数传入的节点的子节点列表数组。
  stack:        主函数传入的各个数值的栈空间。
  result:       主函数传入的需要计算的结果数组，最后要计算的就是result[i]。
  局部变量deepest初始化为-1，因为根节点的层级为0，也可能是结果。 */
static void recursionCalc(int *nums, int *layer, int i, struct LinkedNode **children, struct SoloStack *stack, int *result)
{
    int x = 0, y = 0, deepest = -1;
    struct LinkedNode *node = NULL;
    /* 先处理当前节点，遍历当前节点所有的互质数。 */
    for(x = 0; gPrimeSize[nums[i]] > x; x++)
    {
        /* 这个互质数，如果在上层出现过，取栈顶的那个，那result[i]必然有结果。 */
        y = gPrime[nums[i]][x];
        if(0 < stack[y].arrSize && deepest < layer[stack[y].arr[stack[y].arrSize - 1]])
        {
            deepest = layer[stack[y].arr[stack[y].arrSize - 1]];
            result[i] = stack[y].arr[stack[y].arrSize - 1];
        }
    }
    /* 把当前节点加入到数组中，然后调用当前节点的各个子节点。 */
    stackPush(&stack[nums[i]], i);
    for(node = children[i]; NULL != node; node = node->next)
    {
        /* 不要反过来调用父节点，避免嵌套循环。 */
        if(layer[i] < layer[node->index])
        {
            recursionCalc(nums, layer, node->index, children, stack, result);
        }
    }
    /* 调用完子节点之后，重新把这个节点出栈，因为当前节点只对自己的子节点的结果产生影响，不影响树种的其他节点。 */
    stackPop(&stack[nums[i]]);
    return;
}
 Comments
On this page
1766-互质树