در این مطلب، ویدئو تمرین برنامه نویسی پایتون: LeetCode #104 — حداکثر عمق درخت باینری با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:09:47
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:02,080 –> 00:00:04,640
سلام به همه و به تمرین برنامه نویسی پایتون خوش آمدید
2
00:00:04,640 –> 00:00:06,160
3
00:00:06,160 –> 00:00:08,960
در این قسمت ما قصد داریم
4
00:00:08,960 –> 00:00:09,280
5
00:00:09,280 –> 00:00:12,880
کد لید شماره 104 حداکثر عمق
6
00:00:12,880 –> 00:00:16,400
درخت باینری را انجام دهیم این به عنوان یک مشکل آسان طبقه بندی می شود.
7
00:00:16,400 –> 00:00:17,600
8
00:00:17,600 –> 00:00:19,199
9
00:00:19,199 –> 00:00:20,640
10
00:00:20,640 –> 00:00:24,080
11
00:00:24,080 –> 00:00:24,880
12
00:00:24,880 –> 00:00:27,599
عمق حداکثر عمق تعداد گرههایی است که
13
00:00:27,599 –> 00:00:29,279
در طول طولانیترین مسیر
14
00:00:29,279 –> 00:00:31,679
از گره ریشه تا دورترین
15
00:00:31,679 –> 00:00:32,960
16
00:00:32,960 –> 00:00:36,000
گره برگ است.
17
00:00:36,000 –> 00:00:37,840
18
00:00:37,840 –> 00:00:39,360
19
00:00:39,360 –> 00:00:42,160
20
00:00:42,160 –> 00:00:44,320
نمایش آن در اینجا بنابراین نت ریشه
21
00:00:44,320 –> 00:00:45,440
22
00:00:45,440 –> 00:00:48,480
سه است و دو فرزند نه و بیست دارد
23
00:00:48,480 –> 00:00:49,360
و گره بیست
24
00:00:49,360 –> 00:00:52,079
دو فرزند دیگر پانزده و هفت دارد
25
00:00:52,079 –> 00:00:53,199
و با
26
00:00:53,199 –> 00:00:55,600
توجه به این درخت حداکثر عمق آن
27
00:00:55,600 –> 00:00:57,600
سه است زیرا در اینجا سه سطح داریم نت
28
00:00:57,600 –> 00:01:00,480
یشه سطح یک است. نه و
29
00:01:00,480 –> 00:01:01,920
بیست در سطح دو
30
00:01:01,920 –> 00:01:05,119
و پانزده و هفت در سطح سه هستند،
31
00:01:05,119 –> 00:01:05,760
بنابراین
32
00:01:05,760 –> 00:01:07,600
با توجه به این درخت باینری در اینجا،
33
00:01:07,600 –> 00:01:08,799
سه را برمی گردانیم،
34
00:01:08,799 –> 00:01:10,720
بنابراین بیایید با رفتن به
35
00:01:10,720 –> 00:01:12,799
ویرایشگر کد و g شروع کنیم. تخته سفید
36
00:01:12,799 –> 00:01:14,240
خود را در اینجا قرار می دهیم تا به این فکر
37
00:01:14,240 –> 00:01:17,200
کنیم که چگونه می توانیم به این مشکل نزدیک شویم، بنابراین یک
38
00:01:17,200 –> 00:01:18,479
درخت
39
00:01:18,479 –> 00:01:20,320
باینری یک ساختار داده است که در آن مقداری
40
00:01:20,320 –> 00:01:22,159
گره ریشه وجود دارد و سپس
41
00:01:22,159 –> 00:01:24,479
گره ریشه می تواند تا دو گره فرزند داشته باشد
42
00:01:24,479 –> 00:01:26,000
که از
43
00:01:26,000 –> 00:01:28,400
آن منشعب می شوند و آن گره های فرزند نیز می توانند
44
00:01:28,400 –> 00:01:29,600
بچه داشته باشید
45
00:01:29,600 –> 00:01:32,320
و می تواند اساساً تا عمق دلخواه رشد کند،
46
00:01:32,320 –> 00:01:33,840
47
00:01:33,840 –> 00:01:36,560
بنابراین این مشکل این است که بفهمیم
48
00:01:36,560 –> 00:01:38,560
درخت واقعاً چقدر عمق دارد،
49
00:01:38,560 –> 00:01:41,200
بنابراین بیایید یک درخت باینری کوچک را
50
00:01:41,200 –> 00:01:42,720
در اینجا ترسیم کنیم و به این فکر
51
00:01:42,720 –> 00:01:45,119
کنیم که چگونه می توانیم به این مشکل نزدیک شویم،
52
00:01:45,119 –> 00:01:46,320
به عنوان مثال
53
00:01:46,320 –> 00:01:48,960
این درست در اینجا یک مشکل است. مثالی از
54
00:01:48,960 –> 00:01:49,520
55
00:01:49,520 –> 00:01:52,000
درخت دودویی که به ما داده می شود
56
00:01:52,000 –> 00:01:54,399
درخت باینری متعادل یا کامل نیست زیرا
57
00:01:54,399 –> 00:01:55,200
58
00:01:55,200 –> 00:01:57,040
این شاخه در اینجا دارد که اتفاقاً
59
00:01:57,040 –> 00:01:59,280
عمیق تر می شود و این شاخه در اینجا به
60
00:01:59,280 –> 00:02:00,159
همان اندازه عمیق نمی رود
61
00:02:00,159 –> 00:02:03,439
اما این هنوز یک باینری است. درختی که
62
00:02:03,439 –> 00:02:05,360
به طور بالقوه می تواند به عنوان ورودی
63
00:02:05,360 –> 00:02:06,880
این مشکل ارسال شود، بنابراین ما
64
00:02:06,880 –> 00:02:09,280
باید بتوانیم با مواردی که
65
00:02:09,280 –> 00:02:12,080
سطوح در هر دو طرف متعادل نیستند مقابله کنیم،
66
00:02:12,080 –> 00:02:15,120
بنابراین عمق یک درخت باینری دقیقا
67
00:02:15,120 –> 00:02:15,599
68
00:02:15,599 –> 00:02:17,360
چقدر است و چگونه می توانیم به آن بپردازیم. آن را به خوبی محاسبه کنیم،
69
00:02:17,360 –> 00:02:19,200
بنابراین وقتی در نت اصلی
70
00:02:19,200 –> 00:02:20,000
اینجا هستیم، تنها چیزی که می
71
00:02:20,000 –> 00:02:23,280
دانیم این است که یک سطح برای یافتن
72
00:02:23,280 –> 00:02:24,480
حداکثر عمقی
73
00:02:24,480 –> 00:02:26,879
که باید به آن اضافه کنیم در هر سطح زیر
74
00:02:26,879 –> 00:02:29,360
آن داریم و نمی توانیم فوراً بررسی کنیم که چه چیزی
75
00:02:29,360 –> 00:02:30,000
76
00:02:30,000 –> 00:02:31,840
در آن است. گره ریشه چون باید
77
00:02:31,840 –> 00:02:33,519
از درخت عبور کنیم
78
00:02:33,519 –> 00:02:36,560
تا بفهمیم حداکثر عمق چقدر است، بنابراین
79
00:02:36,560 –> 00:02:39,280
وقتی اینجا هستیم میتوانیم بگوییم که عمق
80
00:02:39,280 –> 00:02:39,920
یک داریم
81
00:02:39,920 –> 00:02:41,920
و سپس میخواهیم هر چه
82
00:02:41,920 –> 00:02:44,400
حداکثر از عمق دو
83
00:02:44,400 –> 00:02:45,280
فرزند است به آن اضافه کنیم.
84
00:02:45,280 –> 00:02:49,519
بنابراین ما میخواهیم حداکثر
85
00:02:49,680 –> 00:02:53,599
عمق دو شاخه فرزند را در اینجا اضافه کنیم،
86
00:02:53,599 –> 00:02:55,760
بنابراین باید به آنها پیمایش کنیم
87
00:02:55,760 –> 00:02:57,360
و حداکثر آنها
88
00:02:57,360 –> 00:02:57,840
89
00:02:57,840 –> 00:03:00,000
را بفهمیم، بنابراین وقتی اینجا هستیم باید تا 10 پیمایش
90
00:03:00,000 –> 00:03:02,000
کنیم. یکی را اضافه کنید زیرا ده
91
00:03:02,000 –> 00:03:03,360
یک سطح جدید است،
92
00:03:03,360 –> 00:03:05,599
اما پس از آن باید
93
00:03:05,599 –> 00:03:06,800
بگوییم که
94
00:03:06,800 –> 00:03:09,040
حداکثر عمق دهها کودک چقدر است خوب در این
95
00:03:09,040 –> 00:03:10,640
مورد 10 هیچ فرزندی
96
00:03:10,640 –> 00:03:12,239
ندارد بنابراین چیزی اضافه نمیکند
97
00:03:12,239 –> 00:03:14,640
و وقتی بدانیم که حداکثر عمق
98
00:03:14,640 –> 00:03:15,440
این
99
00:03:15,440 –> 00:03:18,879
شاخه 1 است، بنابراین ما به بالا گزارش می دهیم
100
00:03:18,879 –> 00:03:21,360
که حداکثر عمق برت این شاخه
101
00:03:21,360 –> 00:03:22,400
یک است
102
00:03:22,400 –> 00:03:23,920
و سپس ما باید از این طرف
103
00:03:23,920 –> 00:03:25,519
نیز عبور کنیم، بنابراین از این طرف پایین میرویم
104
00:03:25,519 –> 00:03:27,680
و میگوییم درست در هفت هستیم که به علاوه
105
00:03:27,680 –> 00:03:28,799
یک برای این
106
00:03:28,799 –> 00:03:30,799
سطح، حداکثر حداکثر دو فرزندش که
107
00:03:30,799 –> 00:03:32,480
باید به پایین طی کنیم، هستیم. بگو
108
00:03:32,480 –> 00:03:34,080
خوب اینجا به علاوه یک است،
109
00:03:34,080 –> 00:03:36,159
اینجا به علاوه یک اینجاست، ما باید دوباره ما را رد کنیم
110
00:03:36,159 –> 00:03:37,200
111
00:03:37,200 –> 00:03:39,760
و در نهایت متوجه شویم که
112
00:03:39,760 –> 00:03:41,200
چیزی در آن پایین وجود ندارد
113
00:03:41,200 –> 00:03:42,879
و این اعداد باید به
114
00:03:42,879 –> 00:03:44,400
سمت بالا جمع شوند
115
00:03:44,400 –> 00:03:47,120
تا برای آن یکی دو شود و برای آن یکی
116
00:03:47,120 –> 00:03:48,319
،
117
00:03:48,319 –> 00:03:51,040
سپس سه شود. و در نهایت
118
00:03:51,040 –> 00:03:52,400
می بینیم که حداکثر
119
00:03:52,400 –> 00:03:54,959
بین این شاخه و این شاخه
120
00:03:54,959 –> 00:03:56,400
این طرف است زیرا اینجا سه مورد وج
121
00:03:56,400 –> 00:03:58,239
د دارد و اینجا فقط یکی وجود دارد که
122
00:03:58,239 –> 00:04:00,400
ه بالا برمی گردد و س
123
00:04:00,400 –> 00:04:01,599
به
124
00:04:01,599 –> 00:04:03,920
ضافه گره ریشه اصلی ما چه
125
00:04:03,920 –> 00:04:05,680
ر عمق برای این کل خواهد بود. در
126
00:04:05,680 –> 00:04:08,239
اما چگونه میتوان این کار را در کد انجام داد،
127
00:04:08,239 –> 00:04:10,159
بنابراین این نوع مشکل
128
00:04:10,159 –> 00:04:11,439
به طور طبیعی به انجام
129
00:04:11,439 –> 00:04:14,400
یک الگوریتم بازگشتی کمک میکند که در آن ما میتوانیم
130
00:04:14,400 –> 00:04:15,040
131
00:04:15,040 –> 00:04:17,040
تا انتهای گره را دریل کنیم
132
00:04:17,040 –> 00:04:19,120
و سپس نتایج
133
00:04:19,120 –> 00:04:22,479
را به سمت بالا به سمت فی بسازیم. و پاسخ چیست،
134
00:04:22,479 –> 00:04:25,520
بنابراین ما از گره ریشه شروع می کنیم و می
135
00:04:25,520 –> 00:04:28,560
گوییم در سطح یک هستیم، اما برای
136
00:04:28,560 –> 00:04:31,280
اینکه بفهمیم حداکثر دو فرزند چقدر
137
00:04:31,280 –> 00:04:32,080
138
00:04:32,080 –> 00:04:33,759
خوب هستند، نمی توانیم این کار را فقط با
139
00:04:33,759 –> 00:04:35,520
نگاه کردن به کودک انجام دهیم. باید
140
00:04:35,520 –> 00:04:37,280
تمام مسیر را به سمت پایین به سمت پایین طی کنیم
141
00:04:37,280 –> 00:04:38,639
142
00:04:38,639 –> 00:04:41,040
تا بتوانیم این کار را انجام دهیم تا بتوانیم از یک
143
00:04:41,040 –> 00:04:42,320
ساختار الگوریتم بازگشتی استفاده
144
00:04:42,320 –> 00:04:44,800
کنیم که در آن همان الگوریتم حداکثر عمق
145
00:04:44,800 –> 00:04:47,199
را روی قسمت کوچکتری
146
00:04:47,199 –> 00:04:49,600
از درخت اجرا می کنیم و سپس در نهایت
147
00:04:49,600 –> 00:04:51,759
به برخی از موارد پایه
148
00:04:51,759 –> 00:04:53,919
که در آن درختی باقی نمانده است و سپس
149
00:04:53,91