-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path116_PopulateNextRightPointer.py
More file actions
294 lines (281 loc) · 27.9 KB
/
Copy path116_PopulateNextRightPointer.py
File metadata and controls
294 lines (281 loc) · 27.9 KB
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
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
"""
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The
binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be
set to NULL.
Initially, all next pointers are set to NULL.
"""
from typing import List, Optional
from _Binary_Tree import TreeNode, ConstructTree, TREE_NODE_TYPE
def connect_next_pointer(root: Optional[TreeNode]) -> Optional[TreeNode]:
"""
:param root: root of a perfect binary tree: all leaves are on the same level and every parent has two children
:return: same root, with each nodes adding a next pointer to the node right next to it
"""
if root is None:
return None
root.next = None
parent_level_left = root
children_level_left = root.left
while parent_level_left and children_level_left:
current_parent = parent_level_left
while current_parent:
current_parent.left.next = current_parent.right
current_parent.right.next = current_parent.next.left if current_parent.next else None
current_parent = current_parent.next
parent_level_left = children_level_left
children_level_left = children_level_left.left
return root
def generate_output_format(root: TreeNode) -> List[TREE_NODE_TYPE]:
"""
:return: used to compare to expected output
"""
return_list = []
while root:
current_node = root
while current_node:
return_list.append(current_node.val)
current_node = current_node.next
return_list.append('#')
root = root.left
return return_list
test_cases = [([1, 2, 3, 4, 5, 6, 7], [1, '#', 2, 3, '#', 4, 5, 6, 7, '#']),
([1], [1, '#']),
([], []),
([37, 27, 87, 41, 56, 36, 55, 21, 27, 85, 62, 96, 36, 61, 85, 60, 41, 91, 98, 21, 32, 49, 13, 70, 13, 98,
51, 51, 6, 21, 56, 95, 92, 81, 23, 69, 1, 32, 37, 6, 82, 44, 94, 83, 34, 3, 44, 95, 94, 8, 42, 20, 11,
41, 18, 61, 83, 42, 39, 47, 54, 37, 26],
[37, '#', 27, 87, '#', 41, 56, 36, 55, '#', 21, 27, 85, 62, 96, 36, 61, 85, '#', 60, 41, 91, 98, 21, 32,
49, 13, 70, 13, 98, 51, 51, 6, 21, 56, '#', 95, 92, 81, 23, 69, 1, 32, 37, 6, 82, 44, 94, 83, 34, 3, 44,
95, 94, 8, 42, 20, 11, 41, 18, 61, 83, 42, 39, 47, 54, 37, 26, '#']),
([311, -364, 807, 14, -922, -618, -270, -965, 114, 584, -507, -589, 638, 54, -193, 920, 920, 997, -349,
144, 915, -47, 94, -200, -285, 560, -760, -371, 189, -470, -746, 588, -723, -958, -614, 362, -729, -976,
-640, -319, 911, -819, 851, -293, -14, 323, -496, -105, 135, -180, -55, 255, 822, -643, 827, -104, -555,
-800, -42, 559, 86, -512, -758, -786, 33, 483, -354, 543, -970, 633, 273, -617, 929, -944, -797, 684,
105, -745, -459, 317, 556, 823, 988, 595, 1, -455, -621, -727, 603, 786, -769, -956, 786, 234, 482,
-307, 467, -343, 778, 692, -937, -650, -928, -719, -565, -145, 789, 718, -900, -842, 254, 295, 877, 671,
577, 367, -476, -701, 300, -4, 618, 731, 793, -57, -788, 184, 516, 796, 858, 135, -825, 60, -217, -764,
-577, 816, -735, 46, 637, 895, -670, 870, -629, 442, -501, -309, -37, 485, -110, -25, -877, -926, 943,
359, 213, -260, -648, -135, -244, -885, -603, -567, 669, -259, -830, 998, -254, -845, 871, 707, -453,
655, 87, -2, 753, 466, 988, 133, -1000, 504, 160, 773, -776, 764, 426, -839, -274, -802, -395, -774,
416, -229, -335, -381, -1000, 239, 836, -435, -733, 589, 291, -860, -710, 926, 327, 820, 41, -157, -708,
-955, 939, 925, -785, 399, -784, 618, -105, 706, -226, -171, -644, -151, 504, 915, 530, 994, -999, 369,
262, -24, 32, 559, -538, -954, 140, 217, 689, -860, 917, -779, -442, -668, 841, -835, -600, 11, 792,
-578, -672, 987, -238, 261, 55, 652, 518, -666, 17, -262, -42, 362, 927, -934, 770, -849, -273, 45,
-865, -968, -554, 473, -705, 63, -744, -496, -82, -35, 645, -638, -725, -323, 523, 219, -182, 917, 354,
-41, -729, -175, 93, -12, -529, -559, -593, -705, -857, 17, 506, -21, -59, 227, -446, -617, -888, -258,
-856, 805, -944, -844, 88, 531, 41, 87, -311, 612, 708, -441, -543, -579, 757, -327, -162, -755, -104,
-328, -815, -390, 778, -883, -695, 95, -964, -263, -965, 55, 419, 91, 516, -637, 36, 805, 463, -526,
403, -309, 697, 717, -896, 717, 596, -239, 452, -255, 321, 292, 910, -267, -757, 517, -39, 173, 602,
901, 967, -843, -72, -61, 67, -609, -589, 19, -582, 477, 45, 931, -410, 398, -403, -64, -349, -4, 782,
253, -693, -905, -751, -697, 541, -368, 405, -337, 491, -477, 558, -667, 752, -777, 423, 378, 194, 593,
-965, -995, 421, 540, 448, -562, -453, -31, 72, 25, -324, 553, 304, -661, 12, -327, -656, -796, 77,
-688, -318, 488, 51, 805, 517, -547, 971, -277, 218, 39, 841, -655, -763, 664, -103, -348, 954, 121,
890, -612, -870, -103, -39, -838, 548, -846, 667, -687, -983, -776, -175, 631, 611, -434, 750, 572, 103,
-787, 857, -293, 417, 13, -92, -829, -40, -835, 42, 534, -812, 127, -450, -641, 192, -146, 926, -47,
289, -663, -734, 617, -77, -199, 416, 532, -795, 185, -961, 558, 226, 272, -320, 541, -125, 223, 71, 65,
872, 308, 351, -888, -119, 128, 67, -412, -468, -645, 858, 637, -54, -489, 719, -187, 138, -180, 177,
-963, 480, 730, 480, -145, -834, -987, -669, 340, -177, -313, -417, 318, -864, -103, 227, -532, -991,
-867, 656, -252, 934, -91, -773, 442, -185, 186, 862, -634, -548, -35, 631, -369, -106, 297, 642, -795,
-808, -97, -958, -897, 221, -81, 817, 267, -69, 27, -240, -925, -808, 959, 234, 720, -724, 355, 266,
-833, -730, 443, 889, -987, -310, 654, 258, 72, -320, 631, -280, -18, 174, 816, -197, -146, 155, 334,
350, -231, 854, 256, -427, 753, -913, 930, 413, 245, -5, -339, 582, -377, -479, 738, -904, 226, 895,
-167, 227, 923, 100, 387, -675, 460, -938, -380, -248, 783, -312, -811, -252, 422, -352, -21, 458, 604,
901, 246, 979, 976, -411, -269, 855, -995, -80, -102, 71, -619, 282, 828, 617, -286, -674, 31, -899,
965, -967, -354, -150, -284, -778, -349, 297, 74, 542, -351, -407, -161, 172, 792, 596, 367, 151, -708,
868, -814, 870, 418, -702, -795, -968, 755, 413, -650, -847, -594, -792, 28, 903, 906, -616, 121, 0,
-444, -874, 130, 573, -823, -992, -961, -745, 691, -973, 557, -835, 980, -26, -348, -440, 45, 452, 833,
923, 622, 50, -863, 713, -242, -335, -393, -228, -781, -470, 103, 397, 977, -120, -288, 292, 388, 244,
882, 496, -443, -851, 151, -642, 29, -966, 329, -433, -222, 888, -516, -315, 846, 560, -926, -610, 293,
-912, -675, 558, 509, 534, 354, 548, -201, -757, -356, 257, 81, 953, -580, -569, -764, -615, -482, 191,
-865, -599, 73, -948, 252, -403, 110, -118, -260, 153, 750, -964, -830, 669, -928, 873, -547, -382,
-873, 596, -157, 17, -60, 939, 92, 270, -913, -434, 135, -227, 241, 787, -102, 564, 301, -748, 838,
-871, -774, -954, 395, -593, 796, 788, -116, 572, -283, -183, -194, -317, -406, -336, -613, -759, 893,
-820, -579, 92, 211, 194, 533, -58, 80, 398, -802, -301, -324, 700, -675, -289, -677, -897, -708, -8,
983, -542, -496, -295, 6, -135, -959, -542, 766, 477, 235, 78, 64, -12, -466, -697, -755, 627, -120,
400, -999, 611, 795, -443, 255, -984, 12, -194, -990, -436, 582, 45, 511, 716, -631, 648, -957, 236,
-208, 541, -149, -978, -815, 484, 833, -155, 16, 975, 270, 108, -249, 393, 877, 454, -18, 653, -428,
-96, -579, 573, -144, -514, -446, 688, 355, -56, 842, 634, 450, 930, -204, 391, 988, 655, -404, 43,
-687, 650, -294, -861, -140, -473, -929, 826, 19, 453, 481, 180, 313, -117, 191, -77, -824, -354, 209,
-154, 74, -742, 362, 835, 129, 83, 165, 744, 538, 957, -394, 602, 198, -381, -117, -178, 353, 735, 946,
-418, 546, 5, -95, -125, -240, 778, 550, 613, -721, -969, 969, -843, 762, -674, 540, 525, -2, -789,
-687, 920, 306, -944, 855, -104, 45, 921, 980, -706, -412, 52, -165, 926, -622, 338, -727, 276, -835,
31, 331, -909, -741, -481, 402, 415, -72, -123, -917, 174, -612, 277, 841, -711, 582, 683, -816, 749,
-604, 383, 942, 79, 493, -455, 31, 155, 150, 300, -940, 613, -357, 575, -48, -200, 444, -433, 447, 274,
-579, -673, 626, 213, -888, 120, 25, 581, -86, -347, -198, -838, 339, -376, 503, 15, 195, -486, 405,
732, 553, -659, -570, 834, -890, 282, -518, 766, 852, 88, 495, -26, -839, -306, -513, -872, -916, -314,
-984, 622, -44, 31, 51, 957, 608, 712, 414, 950, 647, -513, -886, -379, -194, 358, -69, -490, -563,
-897, 561, -543, 776, -95, 540, 868, 152, -4, 20, 863, 447, 29, -848, 348, 189, 396, 307, -820, 398,
444, -20, -296, 45, 589, 606, -882, -306, 719, 403, 467, -422, -1, 200, 41, 184, 317, -126, 838, 261,
-255, -119, 843, 564, 375, 90, -500, -758, 276, -395, -572, 445, -72, 345, 383, 422, -456, -384, -642,
679, 89, 910, -460, -436, -541, 454, -930, 977, 88, 871, -814, 664, 575, 552, 88, 483, 605, -666, 915,
251, -548, -183, 573, -490, 842, 168, -15, 338, -3, 540, -556, -187, 931, 630, -640, 424, 848, -999,
-926, -4, -165, 514, 938, 662, 452, -820, -924, 793, -88, 201, 488, 129, -227, 446, -397, 147, 59, 390,
166, 443, 569, 466, 99, -230, 703, -291, 929, -857, -158, -625, 305, 449, 336, -846, 20, 670, 717, 168,
261, -591, -975, 234, 454, 328, -937, 11, -530, -824, 200, 566, -374, -241, -417, 585, 195, 180, -760,
551, -123, -715, -988, 635, 174, 622, 959, 568, -263, -949, -366, -605, -877, -563, -645, 908, -351,
-631, -64, 330, -83, -78, 190, -154, -435, 719, 636, 905, 46, -671, -302, -396, 421, 294, -568, 980,
122, -136, -437, 733, -446, 447, 719, 143, 439, -959, -593, 85, -787, -798, -907, -170, 153, 40, -889,
936, 179, 539, 646, 789, 825, 649, -577, 510, -898, -712, 647, -615, -699, 584, 388, 450, -58, -848,
-658, -788, 566, -386, -213, 157, 368, 486, -135, 690, 287, 133, -589, -865, -620, -780, -82, 218, 374,
354, 479, -289, 909, 421, -134, 653, 627, -479, -859, -364, -919, 250, -602, 819, 455, 412, -692, 142,
-547, -206, 836, 292, -872, 612, -469, 853, 466, -648, 461, 903, 773, -352, -196, -305, 298, -649, 221,
-506, 898, 490, -228, -683, 949, -52, 612, -832, 834, 664, 883, 318, -178, 381, -438, -416, -140, 452,
669, 879, -335, -5, 870, 732, -588, -654, 596, -993, -982, -202, -432, 278, -391, -136, 159, -414, 920,
-361, -815, -810, 942, 683, 617, 417, -634, -527, -199, -68, 712, -771, -5, -406, -211, -960, 928, -355,
202, 88, 868, 151, 380, 688, 721, 461, -662, -741, -488, 104, -10, 165, -393, -61, -211, -368, 456,
-399, 231, 310, -366, 744, -206, 107, 506, 930, -797, -303, 277, 488, -353, -230, 688, 577, 291, -33,
-351, -266, -972, -405, 941, -555, -34, -673, -556, -284, -392, 271, -105, -955, -360, 649, -842, 878,
420, 319, -823, 66, 885, -377, 479, -564, 659, -61, -500, 23, -232, 511, 374, 294, -451, -327, -906,
-817, 434, -111, -990, -787, 831, -78, 805, 643, 647, -943, 712, 805, -864, 405, 313, -37, -458, 973,
771, -668, 240, -655, -76, -292, 788, -41, -23, 349, 477, 597, -62, -930, -106, -152, -676, -308, 116,
-813, -395, 528, -864, -278, -273, -897, -444, 870, 971, -245, 458, -449, 637, 218, -189, 436, -261,
748, -287, -280, 5, -861, -903, 118, -728, 964, 753, -699, 528, 55, -28, -238, 574, 577, -67, 69, -374,
912, 402, -57, -612, 814, -175, -163, -932, -801, 359, 693, -860, -257, 773, 752, -689, 203, -583, -532,
-406, -73, -840, 522, -174, 396, -457, 818, -731, 552, 94, -407, 63, 730, -282, 850, -777, -511, 350,
895, 4, -714, -192, 906, 239, 140, -794, 807, -208, 424, 666, -953, -513, -976, 90, 889, 952, -808, 7,
-551, -629, 494, 267, 380, -637, 539, -455, -385, -44, -896, 375, 726, -222, -618, -961, -24, 965, -13,
-273, 644, 42, 736, -426, 597, -939, -368, -229, -923, -16, -39, -59, 613, -178, -623, -936, 671, 266,
-195, 903, 402, -772, -178, 436, -161, 792, -648, 733, -823, 443, -795, 567, 818, -129, 674, -622, -817,
325, -909, -110, 365, 553, -890, -958, 427, -452, -772, 934, 581, 115, -237, -872, -767, -826, -645,
586, 841, 573, -494, 344, 863, -752, 815, -657, -863, -608, 577, -862, -674, -901, -817, -361, -184,
557, 660, 485, 411, 153, 143, 159, 689, -572, 434, -987, -828, -67, 34, -302, 570, -404, 153, 418, -11,
888, 659, 974, 995, -877, -287, 69, 356, 405, -821, 454, -337, 970, 922, -636, 656, -293, 62, 333, 338,
-376, -43, -280, -311, 106, -362, -93, 428, -651, -279, -264, -386, 713, -905, -127, -986, -892, 960,
-950, -889, 19, 118, -863, 396, 922, 753, 706, -220, 478, 983, -120, 951, -100, 114, 735, -398, -768,
602, 623, -152, 754, 656, -465, -353, -24, 770, -62, -280, 290, -107, 397, -314, 248, 901, 884, 43, 267,
815, 394, 678, -574, -234, -614, 646, 568, 917, -148, -386, -264, 764, 109, -47, -807, -10, -688, 167,
256, -986, 355, -530, 654, -361, -862, -470, -960, -207, -989, -338, -494, 185, -692, 618, -218, -826,
901, 903, 301, 201, 624, 257, -577, -813, -248, 203, 243, -743, -652, 265, 161, 415, -220, -889, -811,
978, -792, 386, -761, 744, -373, -21, -103, -749, -814, -727, 507, -330, -108, 438, -217, -102, -386,
574, -413, 369, -144, 55, -715, -907, 672, 50, 847, 113, 410, -300, -9, 817, -947, -480, -384, 904, 135,
724, 108, -990, -149, -570, -751, 67, -643, 735, 881, -853, 438, -673, 797, -975, -952, 894, 47, -830,
-800, -867, 443, 776, -283, 411, 71, 950, -183, 361, -435, -444, 195, -733, -755, -151, 550, -183, -434,
32, 683, 934, 392, -811, -941, -912, -296, -392, -788, -756, 189, 54, -486, -202, 884, -883, -559, 674,
130, -101, -666, -420, 828, 135, -142, -604, -754, -917, 87, -43, 132, 610, 808, 32, 69, -467, 306, 627,
719, -607, 473, 151, -772, 890, -502, -420, -402, -225, 341, -135, 4, -784, 756, -64, -907, -307, 71,
-559, -996, 805, -231, 526, 289, 924, -108, 339, 880, -898, -64, -767, -762, 449, -325, 543, -673, -633,
395, 208, 190, -982, 741, 504, -385, 416, 71],
[311, '#', -364, 807, '#', 14, -922, -618, -270, '#', -965, 114, 584, -507, -589, 638, 54, -193, '#',
920, 920, 997, -349, 144, 915, -47, 94, -200, -285, 560, -760, -371, 189, -470, -746, '#', 588, -723,
-958, -614, 362, -729, -976, -640, -319, 911, -819, 851, -293, -14, 323, -496, -105, 135, -180, -55,
255, 822, -643, 827, -104, -555, -800, -42, 559, 86, -512, -758, '#', -786, 33, 483, -354, 543, -970,
633, 273, -617, 929, -944, -797, 684, 105, -745, -459, 317, 556, 823, 988, 595, 1, -455, -621, -727,
603, 786, -769, -956, 786, 234, 482, -307, 467, -343, 778, 692, -937, -650, -928, -719, -565, -145, 789,
718, -900, -842, 254, 295, 877, 671, 577, 367, -476, -701, 300, -4, 618, 731, 793, -57, -788, 184, 516,
'#', 796, 858, 135, -825, 60, -217, -764, -577, 816, -735, 46, 637, 895, -670, 870, -629, 442, -501,
-309, -37, 485, -110, -25, -877, -926, 943, 359, 213, -260, -648, -135, -244, -885, -603, -567, 669,
-259, -830, 998, -254, -845, 871, 707, -453, 655, 87, -2, 753, 466, 988, 133, -1000, 504, 160, 773,
-776, 764, 426, -839, -274, -802, -395, -774, 416, -229, -335, -381, -1000, 239, 836, -435, -733, 589,
291, -860, -710, 926, 327, 820, 41, -157, -708, -955, 939, 925, -785, 399, -784, 618, -105, 706, -226,
-171, -644, -151, 504, 915, 530, 994, -999, 369, 262, -24, 32, 559, -538, -954, 140, 217, 689, -860,
917, -779, -442, -668, 841, -835, -600, 11, 792, -578, -672, 987, -238, 261, 55, 652, 518, '#', -666,
17, -262, -42, 362, 927, -934, 770, -849, -273, 45, -865, -968, -554, 473, -705, 63, -744, -496, -82,
-35, 645, -638, -725, -323, 523, 219, -182, 917, 354, -41, -729, -175, 93, -12, -529, -559, -593, -705,
-857, 17, 506, -21, -59, 227, -446, -617, -888, -258, -856, 805, -944, -844, 88, 531, 41, 87, -311, 612,
708, -441, -543, -579, 757, -327, -162, -755, -104, -328, -815, -390, 778, -883, -695, 95, -964, -263,
-965, 55, 419, 91, 516, -637, 36, 805, 463, -526, 403, -309, 697, 717, -896, 717, 596, -239, 452, -255,
321, 292, 910, -267, -757, 517, -39, 173, 602, 901, 967, -843, -72, -61, 67, -609, -589, 19, -582, 477,
45, 931, -410, 398, -403, -64, -349, -4, 782, 253, -693, -905, -751, -697, 541, -368, 405, -337, 491,
-477, 558, -667, 752, -777, 423, 378, 194, 593, -965, -995, 421, 540, 448, -562, -453, -31, 72, 25,
-324, 553, 304, -661, 12, -327, -656, -796, 77, -688, -318, 488, 51, 805, 517, -547, 971, -277, 218, 39,
841, -655, -763, 664, -103, -348, 954, 121, 890, -612, -870, -103, -39, -838, 548, -846, 667, -687,
-983, -776, -175, 631, 611, -434, 750, 572, 103, -787, 857, -293, 417, 13, -92, -829, -40, -835, 42,
534, -812, 127, -450, -641, 192, -146, 926, -47, 289, -663, -734, 617, -77, -199, 416, 532, -795, 185,
-961, 558, 226, 272, -320, 541, -125, 223, 71, 65, 872, 308, 351, -888, -119, 128, 67, -412, -468, -645,
858, 637, -54, -489, 719, '#', -187, 138, -180, 177, -963, 480, 730, 480, -145, -834, -987, -669, 340,
-177, -313, -417, 318, -864, -103, 227, -532, -991, -867, 656, -252, 934, -91, -773, 442, -185, 186,
862, -634, -548, -35, 631, -369, -106, 297, 642, -795, -808, -97, -958, -897, 221, -81, 817, 267, -69,
27, -240, -925, -808, 959, 234, 720, -724, 355, 266, -833, -730, 443, 889, -987, -310, 654, 258, 72,
-320, 631, -280, -18, 174, 816, -197, -146, 155, 334, 350, -231, 854, 256, -427, 753, -913, 930, 413,
245, -5, -339, 582, -377, -479, 738, -904, 226, 895, -167, 227, 923, 100, 387, -675, 460, -938, -380,
-248, 783, -312, -811, -252, 422, -352, -21, 458, 604, 901, 246, 979, 976, -411, -269, 855, -995, -80,
-102, 71, -619, 282, 828, 617, -286, -674, 31, -899, 965, -967, -354, -150, -284, -778, -349, 297, 74,
542, -351, -407, -161, 172, 792, 596, 367, 151, -708, 868, -814, 870, 418, -702, -795, -968, 755, 413,
-650, -847, -594, -792, 28, 903, 906, -616, 121, 0, -444, -874, 130, 573, -823, -992, -961, -745, 691,
-973, 557, -835, 980, -26, -348, -440, 45, 452, 833, 923, 622, 50, -863, 713, -242, -335, -393, -228,
-781, -470, 103, 397, 977, -120, -288, 292, 388, 244, 882, 496, -443, -851, 151, -642, 29, -966, 329,
-433, -222, 888, -516, -315, 846, 560, -926, -610, 293, -912, -675, 558, 509, 534, 354, 548, -201, -757,
-356, 257, 81, 953, -580, -569, -764, -615, -482, 191, -865, -599, 73, -948, 252, -403, 110, -118, -260,
153, 750, -964, -830, 669, -928, 873, -547, -382, -873, 596, -157, 17, -60, 939, 92, 270, -913, -434,
135, -227, 241, 787, -102, 564, 301, -748, 838, -871, -774, -954, 395, -593, 796, 788, -116, 572, -283,
-183, -194, -317, -406, -336, -613, -759, 893, -820, -579, 92, 211, 194, 533, -58, 80, 398, -802, -301,
-324, 700, -675, -289, -677, -897, -708, -8, 983, -542, -496, -295, 6, -135, -959, -542, 766, 477, 235,
78, 64, -12, -466, -697, -755, 627, -120, 400, -999, 611, 795, -443, 255, -984, 12, -194, -990, -436,
582, 45, 511, 716, -631, 648, -957, 236, -208, 541, -149, -978, -815, 484, 833, -155, 16, 975, 270, 108,
-249, 393, 877, 454, -18, 653, -428, -96, -579, 573, -144, -514, -446, 688, 355, -56, 842, 634, 450,
930, -204, 391, 988, 655, -404, 43, -687, 650, -294, -861, -140, -473, -929, 826, 19, 453, 481, 180,
313, -117, 191, -77, -824, -354, 209, -154, 74, -742, 362, 835, 129, 83, 165, 744, 538, 957, -394, 602,
198, -381, -117, -178, 353, 735, 946, -418, 546, 5, -95, -125, -240, 778, 550, 613, -721, -969, 969,
-843, 762, -674, 540, 525, -2, -789, -687, 920, 306, -944, 855, -104, 45, 921, 980, -706, -412, 52,
-165, 926, -622, 338, -727, 276, -835, 31, 331, -909, -741, -481, 402, 415, -72, -123, -917, 174, -612,
277, 841, -711, 582, 683, -816, 749, -604, 383, 942, 79, 493, -455, 31, 155, 150, 300, -940, 613, -357,
575, -48, -200, '#', 444, -433, 447, 274, -579, -673, 626, 213, -888, 120, 25, 581, -86, -347, -198,
-838, 339, -376, 503, 15, 195, -486, 405, 732, 553, -659, -570, 834, -890, 282, -518, 766, 852, 88, 495,
-26, -839, -306, -513, -872, -916, -314, -984, 622, -44, 31, 51, 957, 608, 712, 414, 950, 647, -513,
-886, -379, -194, 358, -69, -490, -563, -897, 561, -543, 776, -95, 540, 868, 152, -4, 20, 863, 447, 29,
-848, 348, 189, 396, 307, -820, 398, 444, -20, -296, 45, 589, 606, -882, -306, 719, 403, 467, -422, -1,
200, 41, 184, 317, -126, 838, 261, -255, -119, 843, 564, 375, 90, -500, -758, 276, -395, -572, 445, -72,
345, 383, 422, -456, -384, -642, 679, 89, 910, -460, -436, -541, 454, -930, 977, 88, 871, -814, 664,
575, 552, 88, 483, 605, -666, 915, 251, -548, -183, 573, -490, 842, 168, -15, 338, -3, 540, -556, -187,
931, 630, -640, 424, 848, -999, -926, -4, -165, 514, 938, 662, 452, -820, -924, 793, -88, 201, 488, 129,
-227, 446, -397, 147, 59, 390, 166, 443, 569, 466, 99, -230, 703, -291, 929, -857, -158, -625, 305, 449,
336, -846, 20, 670, 717, 168, 261, -591, -975, 234, 454, 328, -937, 11, -530, -824, 200, 566, -374,
-241, -417, 585, 195, 180, -760, 551, -123, -715, -988, 635, 174, 622, 959, 568, -263, -949, -366, -605,
-877, -563, -645, 908, -351, -631, -64, 330, -83, -78, 190, -154, -435, 719, 636, 905, 46, -671, -302,
-396, 421, 294, -568, 980, 122, -136, -437, 733, -446, 447, 719, 143, 439, -959, -593, 85, -787, -798,
-907, -170, 153, 40, -889, 936, 179, 539, 646, 789, 825, 649, -577, 510, -898, -712, 647, -615, -699,
584, 388, 450, -58, -848, -658, -788, 566, -386, -213, 157, 368, 486, -135, 690, 287, 133, -589, -865,
-620, -780, -82, 218, 374, 354, 479, -289, 909, 421, -134, 653, 627, -479, -859, -364, -919, 250, -602,
819, 455, 412, -692, 142, -547, -206, 836, 292, -872, 612, -469, 853, 466, -648, 461, 903, 773, -352,
-196, -305, 298, -649, 221, -506, 898, 490, -228, -683, 949, -52, 612, -832, 834, 664, 883, 318, -178,
381, -438, -416, -140, 452, 669, 879, -335, -5, 870, 732, -588, -654, 596, -993, -982, -202, -432, 278,
-391, -136, 159, -414, 920, -361, -815, -810, 942, 683, 617, 417, -634, -527, -199, -68, 712, -771, -5,
-406, -211, -960, 928, -355, 202, 88, 868, 151, 380, 688, 721, 461, -662, -741, -488, 104, -10, 165,
-393, -61, -211, -368, 456, -399, 231, 310, -366, 744, -206, 107, 506, 930, -797, -303, 277, 488, -353,
-230, 688, 577, 291, -33, -351, -266, -972, -405, 941, -555, -34, -673, -556, -284, -392, 271, -105,
-955, -360, 649, -842, 878, 420, 319, -823, 66, 885, -377, 479, -564, 659, -61, -500, 23, -232, 511,
374, 294, -451, -327, -906, -817, 434, -111, -990, -787, 831, -78, 805, 643, 647, -943, 712, 805, -864,
405, 313, -37, -458, 973, 771, -668, 240, -655, -76, -292, 788, -41, -23, 349, 477, 597, -62, -930,
-106, -152, -676, -308, 116, -813, -395, 528, -864, -278, -273, -897, -444, 870, 971, -245, 458, -449,
637, 218, -189, 436, -261, 748, -287, -280, 5, -861, -903, 118, -728, 964, 753, -699, 528, 55, -28,
-238, 574, 577, -67, 69, -374, 912, 402, -57, -612, 814, -175, -163, -932, -801, 359, 693, -860, -257,
773, 752, -689, 203, -583, -532, -406, -73, -840, 522, -174, 396, -457, 818, -731, 552, 94, -407, 63,
730, -282, 850, -777, -511, 350, 895, 4, -714, -192, 906, 239, 140, -794, 807, -208, 424, 666, -953,
-513, -976, 90, 889, 952, -808, 7, -551, -629, 494, 267, 380, -637, 539, -455, -385, -44, -896, 375,
726, -222, -618, -961, -24, 965, -13, -273, 644, 42, 736, -426, 597, -939, -368, -229, -923, -16, -39,
-59, 613, -178, -623, -936, 671, 266, -195, 903, 402, -772, -178, 436, -161, 792, -648, 733, -823, 443,
-795, 567, 818, -129, 674, -622, -817, 325, -909, -110, 365, 553, -890, -958, 427, -452, -772, 934, 581,
115, -237, -872, -767, -826, -645, 586, 841, 573, -494, 344, 863, -752, 815, -657, -863, -608, 577,
-862, -674, -901, -817, -361, -184, 557, 660, 485, 411, 153, 143, 159, 689, -572, 434, -987, -828, -67,
34, -302, 570, -404, 153, 418, -11, 888, 659, 974, 995, -877, -287, 69, 356, 405, -821, 454, -337, 970,
922, -636, 656, -293, 62, 333, 338, -376, -43, -280, -311, 106, -362, -93, 428, -651, -279, -264, -386,
713, -905, -127, -986, -892, 960, -950, -889, 19, 118, -863, 396, 922, 753, 706, -220, 478, 983, -120,
951, -100, 114, 735, -398, -768, 602, 623, -152, 754, 656, -465, -353, -24, 770, -62, -280, 290, -107,
397, -314, 248, 901, 884, 43, 267, 815, 394, 678, -574, -234, -614, 646, 568, 917, -148, -386, -264,
764, 109, -47, -807, -10, -688, 167, 256, -986, 355, -530, 654, -361, -862, -470, -960, -207, -989,
-338, -494, 185, -692, 618, -218, -826, 901, 903, 301, 201, 624, 257, -577, -813, -248, 203, 243, -743,
-652, 265, 161, 415, -220, -889, -811, 978, -792, 386, -761, 744, -373, -21, -103, -749, -814, -727,
507, -330, -108, 438, -217, -102, -386, 574, -413, 369, -144, 55, -715, -907, 672, 50, 847, 113, 410,
-300, -9, 817, -947, -480, -384, 904, 135, 724, 108, -990, -149, -570, -751, 67, -643, 735, 881, -853,
438, -673, 797, -975, -952, 894, 47, -830, -800, -867, 443, 776, -283, 411, 71, 950, -183, 361, -435,
-444, 195, -733, -755, -151, 550, -183, -434, 32, 683, 934, 392, -811, -941, -912, -296, -392, -788,
-756, 189, 54, -486, -202, 884, -883, -559, 674, 130, -101, -666, -420, 828, 135, -142, -604, -754,
-917, 87, -43, 132, 610, 808, 32, 69, -467, 306, 627, 719, -607, 473, 151, -772, 890, -502, -420, -402,
-225, 341, -135, 4, -784, 756, -64, -907, -307, 71, -559, -996, 805, -231, 526, 289, 924, -108, 339,
880, -898, -64, -767, -762, 449, -325, 543, -673, -633, 395, 208, 190, -982, 741, 504, -385, 416, 71,
'#']),
]
for connect_next in [connect_next_pointer, ]:
for test_tree_list, expected_output in test_cases:
if test_tree_list:
assert generate_output_format(connect_next(ConstructTree.build_tree_leetcode(test_tree_list).root)) == \
expected_output
else:
assert generate_output_format(connect_next(None)) == expected_output