-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.html
346 lines (328 loc) · 76.5 KB
/
index.html
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
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
<!DOCTYPE html><html lang="en" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>Tree | 一直进步 做喜欢的</title><meta name="keywords" content="Data Structures and Algorithms,LeetCode"><meta name="author" content="贪钱算法还我头发"><meta name="copyright" content="贪钱算法还我头发"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="数据结构——树">
<meta property="og:type" content="article">
<meta property="og:title" content="Tree">
<meta property="og:url" content="https://xfliu1998.github.io/2021/11/01/3-Tree/index.html">
<meta property="og:site_name" content="一直进步 做喜欢的">
<meta property="og:description" content="数据结构——树">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://img.shijue.me/426930d8af0f4e2e924dd3c6bf8b2aaa_d.jpg!dp6">
<meta property="article:published_time" content="2021-11-01T11:56:34.000Z">
<meta property="article:modified_time" content="2023-05-19T13:08:16.430Z">
<meta property="article:author" content="贪钱算法还我头发">
<meta property="article:tag" content="Data Structures and Algorithms">
<meta property="article:tag" content="LeetCode">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://img.shijue.me/426930d8af0f4e2e924dd3c6bf8b2aaa_d.jpg!dp6"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://xfliu1998.github.io/2021/11/01/3-Tree/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: {"path":"search.xml","languages":{"hits_empty":"We didn't find any results for the search: ${query}"}},
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
copy: {
success: 'Copy successfully',
error: 'Copy error',
noSupport: 'The browser does not support'
},
relativeDate: {
homepage: false,
post: false
},
runtime: 'days',
date_suffix: {
just: 'Just',
min: 'minutes ago',
hour: 'hours ago',
day: 'days ago',
month: 'months ago'
},
copyright: undefined,
lightbox: 'fancybox',
Snackbar: undefined,
source: {
jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
justifiedGallery: {
js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
},
fancybox: {
js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
}
},
isPhotoFigcaption: false,
islazyload: false,
isanchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: 'Tree',
isPost: true,
isHome: false,
isHighlightShrink: false,
isToc: true,
postUpdate: '2023-05-19 21:08:16'
}</script><noscript><style type="text/css">
#nav {
opacity: 1
}
.justified-gallery img {
opacity: 1
}
#recent-posts time,
#post-meta time {
display: inline !important
}
</style></noscript><script>(win=>{
win.saveToLocal = {
set: function setWithExpiry(key, value, ttl) {
if (ttl === 0) return
const now = new Date()
const expiryDay = ttl * 86400000
const item = {
value: value,
expiry: now.getTime() + expiryDay,
}
localStorage.setItem(key, JSON.stringify(item))
},
get: function getWithExpiry(key) {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = new Date()
if (now.getTime() > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = url => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
document.head.appendChild(script)
})
win.activateDarkMode = function () {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = function () {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if (GLOBAL_CONFIG_SITE.isHome && /iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/css/pool.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/css/iconfont.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/StaticFile_HEXO@latest/butterfly/js/pool.min.js"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/sviptzk/HexoStaticFile@latest/Hexo/js/mouse_snow.min.js"><link rel="stylesheet" href="/css/custom.css?v1"><link rel="stylesheet" href="//at.alicdn.com/t/font_2264842_b004iy0kk2b.css" media="defer" onload="this.media='all'"><!-- hexo injector head_end start --><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiperstyle.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.css" media="print" onload="this.media='all'"><!-- hexo injector head_end end --><meta name="generator" content="Hexo 5.4.0"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/images/head.jpg" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">Articles</div><div class="length-num">45</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">Tags</div><div class="length-num">12</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">Categories</div><div class="length-num">6</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> Tags</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://img.shijue.me/426930d8af0f4e2e924dd3c6bf8b2aaa_d.jpg!dp6')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">一直进步 做喜欢的</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> Search</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> Home</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> Archives</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> Tags</span></a></div><div class="menus_item"><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> Categories</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">Tree</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">Created</span><time class="post-meta-date-created" datetime="2021-11-01T11:56:34.000Z" title="Created 2021-11-01 19:56:34">2021-11-01</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">Updated</span><time class="post-meta-date-updated" datetime="2023-05-19T13:08:16.430Z" title="Updated 2023-05-19 21:08:16">2023-05-19</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">Word count:</span><span class="word-count">2.1k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">Reading time:</span><span>9min</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="Tree"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">Post View:</span><span id="busuanzi_value_page_pv"></span></span><span class="post-meta-separator">|</span><span class="post-meta-commentcount"><i class="far fa-comments fa-fw post-meta-icon"></i><span class="post-meta-label">Comments:</span><a href="/2021/11/01/3-Tree/#post-comment"><span class="gitalk-comment-count"></span></a></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><p>树一般有两种解题方式:</p>
<ul>
<li>递归:确定递归条件和终止条件</li>
<li>迭代:利用队列或栈这两种数据结构实现,一般层次遍历用队列实现,前序遍历、中序遍历、后序遍历用栈实现</li>
</ul>
<p>稍微复杂的问题般都会结合<strong>DFS</strong>和<strong>回溯</strong></p>
<h1 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h1><ul>
<li>特殊二叉树包括:<ol>
<li>完全⼆叉树(Complete Binary Tree):每⼀层都是紧凑靠左排列,计算节点数的时间复杂度是$O(logN*logN)$</li>
<li>满⼆叉树(Perfect Binary Tree):每层都是是满的,节点数 = 2^树高 - 1,计算节点数的时间复杂度是$O(logN)$</li>
<li>Full Binary Tree:⼆叉树的所有节点要么没有孩⼦节点,要么有两个孩⼦节点</li>
</ol>
</li>
</ul>
<h2 id="二叉树的实现"><a href="#二叉树的实现" class="headerlink" title="二叉树的实现"></a>二叉树的实现</h2><p>以下代码实现了二叉树的初始化及增加节点函数<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span>(<span class="params"><span class="built_in">object</span></span>):</span></span><br><span class="line"> <span class="string">"""节点类"""</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, val=-<span class="number">1</span>, left=<span class="literal">None</span>, right=<span class="literal">None</span></span>):</span></span><br><span class="line"> self.val = val</span><br><span class="line"> self.left = left</span><br><span class="line"> self.right = right</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Tree</span>(<span class="params"><span class="built_in">object</span></span>):</span></span><br><span class="line"> <span class="string">"""树类"""</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self</span>):</span></span><br><span class="line"> self.root = Node()</span><br><span class="line"> self.myQueue = []</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">add</span>(<span class="params">self, val</span>):</span></span><br><span class="line"> <span class="string">"""为树添加节点"""</span></span><br><span class="line"> node = Node(val)</span><br><span class="line"> <span class="keyword">if</span> self.root.val == -<span class="number">1</span>: <span class="comment"># 如果树是空的,则对根节点赋值</span></span><br><span class="line"> self.root = node</span><br><span class="line"> self.myQueue.append(self.root)</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> treeNode = self.myQueue[<span class="number">0</span>] <span class="comment"># 此结点的子树还没有齐</span></span><br><span class="line"> <span class="keyword">if</span> treeNode.left == <span class="literal">None</span>:</span><br><span class="line"> treeNode.left = node</span><br><span class="line"> self.myQueue.append(treeNode.left)</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> treeNode.right = node</span><br><span class="line"> self.myQueue.append(treeNode.right)</span><br><span class="line"> self.myQueue.pop(<span class="number">0</span>) <span class="comment"># 如果该结点存在右子树,将此结点丢弃</span></span><br></pre></td></tr></table></figure></p>
<h2 id="二叉树的遍历"><a href="#二叉树的遍历" class="headerlink" title="二叉树的遍历"></a>二叉树的遍历</h2><h3 id="递归法"><a href="#递归法" class="headerlink" title="递归法"></a>递归法</h3><p>以下代码实现了二叉树的前序(跟左右)、中序(左跟右)、后序(左右跟)遍历<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">front_recursive</span>(<span class="params">self, root</span>):</span></span><br><span class="line"> <span class="string">"""利用递归实现树的先序遍历"""</span></span><br><span class="line"> <span class="keyword">if</span> root <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> <span class="built_in">print</span>(root.val, end=<span class="string">' '</span>)</span><br><span class="line"> self.front_recursive(root.left)</span><br><span class="line"> self.front_recursive(root.right)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">middle_recursive</span>(<span class="params">self, root</span>):</span></span><br><span class="line"> <span class="string">"""利用递归实现树的中序遍历"""</span></span><br><span class="line"> <span class="keyword">if</span> root <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> self.middle_recursive(root.left)</span><br><span class="line"> <span class="built_in">print</span>(root.val, end=<span class="string">' '</span>)</span><br><span class="line"> self.middle_recursive(root.right)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">later_recursive</span>(<span class="params">self, root</span>):</span></span><br><span class="line"> <span class="string">"""利用递归实现树的后序遍历"""</span></span><br><span class="line"> <span class="keyword">if</span> root <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> self.later_recursive(root.left)</span><br><span class="line"> self.later_recursive(root.right)</span><br><span class="line"> <span class="built_in">print</span>(root.val, end=<span class="string">' '</span>)</span><br></pre></td></tr></table></figure></p>
<h3 id="迭代法"><a href="#迭代法" class="headerlink" title="迭代法"></a>迭代法</h3><p>以下代码实现了二叉树的前序、中序、后序、层次遍历<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">front_stack</span>(<span class="params">self, root</span>):</span></span><br><span class="line"> <span class="string">"""利用堆栈实现树的先序遍历"""</span></span><br><span class="line"> <span class="keyword">if</span> root <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> myStack = []</span><br><span class="line"> node = root</span><br><span class="line"> <span class="keyword">while</span> node <span class="keyword">or</span> myStack:</span><br><span class="line"> <span class="keyword">while</span> node: <span class="comment"># 从根节点开始,一直找它的左子树</span></span><br><span class="line"> <span class="built_in">print</span>(node.val, end=<span class="string">' '</span>)</span><br><span class="line"> myStack.append(node)</span><br><span class="line"> node = node.left</span><br><span class="line"> node = myStack.pop() <span class="comment"># while结束表示当前节点node为空,即前一个节点没有左子树了</span></span><br><span class="line"> node = node.right</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">middle_stack</span>(<span class="params">self, root</span>):</span></span><br><span class="line"> <span class="string">"""利用堆栈实现树的中序遍历"""</span></span><br><span class="line"> <span class="keyword">if</span> root <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> myStack = []</span><br><span class="line"> node = root</span><br><span class="line"> <span class="keyword">while</span> node <span class="keyword">or</span> myStack:</span><br><span class="line"> <span class="keyword">while</span> node: <span class="comment"># 从根节点开始,一直找它的左子树</span></span><br><span class="line"> myStack.append(node)</span><br><span class="line"> node = node.left</span><br><span class="line"> node = myStack.pop()</span><br><span class="line"> <span class="built_in">print</span>(node.val, end=<span class="string">' '</span>)</span><br><span class="line"> node = node.right</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">later_stack</span>(<span class="params">self, root</span>):</span></span><br><span class="line"> <span class="string">"""利用堆栈实现树的后序遍历"""</span></span><br><span class="line"> <span class="keyword">if</span> root <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> myStack1 = []</span><br><span class="line"> myStack2 = []</span><br><span class="line"> node = root</span><br><span class="line"> myStack1.append(node)</span><br><span class="line"> <span class="keyword">while</span> myStack1: <span class="comment"># 找出后序遍历的逆序存在myStack2里</span></span><br><span class="line"> node = myStack1.pop()</span><br><span class="line"> <span class="keyword">if</span> node.left:</span><br><span class="line"> myStack1.append(node.left)</span><br><span class="line"> <span class="keyword">if</span> node.right:</span><br><span class="line"> myStack1.append(node.right)</span><br><span class="line"> myStack2.append(node)</span><br><span class="line"> <span class="keyword">while</span> myStack2: <span class="comment"># 将myStack2中的元素出栈,即为后序遍历次序</span></span><br><span class="line"> <span class="built_in">print</span>(myStack2.pop().val, end=<span class="string">' '</span>)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">level_queue</span>(<span class="params">self, root</span>):</span></span><br><span class="line"> <span class="string">"""利用队列实现树的层次遍历"""</span></span><br><span class="line"> l2 = []</span><br><span class="line"> cur_layer = [root]</span><br><span class="line"> <span class="keyword">while</span> cur_layer <span class="keyword">and</span> root:</span><br><span class="line"> l1, next_layer = [], []</span><br><span class="line"> <span class="keyword">for</span> node <span class="keyword">in</span> cur_layer:</span><br><span class="line"> l1.append(node.val)</span><br><span class="line"> <span class="keyword">if</span> node.left:</span><br><span class="line"> next_layer.append(node.left)</span><br><span class="line"> <span class="keyword">if</span> node.right:</span><br><span class="line"> next_layer.append(node.right)</span><br><span class="line"> cur_layer = next_layer</span><br><span class="line"> l2.append(l1)</span><br><span class="line"> <span class="keyword">return</span> l2</span><br></pre></td></tr></table></figure></p>
<h3 id="Morris遍历"><a href="#Morris遍历" class="headerlink" title="Morris遍历"></a>Morris遍历</h3><p>二叉树的递归和迭代遍历都需要借助栈,空间复杂度为$O(h)$,其中$h$指二叉树的最大高度。而Morris遍历的时间复杂度为$O(n)$,空间复杂度为$O(1)$。其遍历规则如下:</p>
<ul>
<li>设当前遍历的节点为cur,若cur无左子树,则<code>cur = cur.right</code></li>
<li>若cur有左子树,找到cur左子树的最右节点记为mostRight<ul>
<li>若mostRight的右子树为空,则令<code>mostRight.right = cur, cur = cur.left</code></li>
<li>若此时<code>mostRight.right = cur</code>,则令<code>mostRight.right = None, cur = cur.right</code></li>
</ul>
</li>
</ul>
<p><strong>代码实现</strong><br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">morris</span>(<span class="params">self, root, order</span>):</span></span><br><span class="line"> <span class="string">"""实现Morris遍历"""</span></span><br><span class="line"> <span class="keyword">if</span> root <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="keyword">return</span></span><br><span class="line"> cur = root</span><br><span class="line"> <span class="keyword">while</span> cur:</span><br><span class="line"> <span class="keyword">if</span> cur.left <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> <span class="built_in">print</span>(cur.val, end=<span class="string">' '</span>)</span><br><span class="line"> cur = cur.right</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> mostRight = cur.left</span><br><span class="line"> <span class="keyword">while</span> mostRight.right <span class="keyword">is</span> <span class="keyword">not</span> <span class="literal">None</span> <span class="keyword">and</span> mostRight.right != cur:</span><br><span class="line"> mostRight = mostRight.right</span><br><span class="line"> <span class="keyword">if</span> mostRight.right <span class="keyword">is</span> <span class="literal">None</span>:</span><br><span class="line"> mostRight.right = cur</span><br><span class="line"> <span class="comment"># 先序遍历</span></span><br><span class="line"> <span class="keyword">if</span> order == <span class="string">'front'</span>:</span><br><span class="line"> <span class="built_in">print</span>(cur.val, end=<span class="string">' '</span>)</span><br><span class="line"> cur = cur.left</span><br><span class="line"> <span class="keyword">elif</span> mostRight.right == cur:</span><br><span class="line"> <span class="comment"># 中序遍历</span></span><br><span class="line"> <span class="keyword">if</span> order == <span class="string">'middle'</span>:</span><br><span class="line"> <span class="built_in">print</span>(cur.val, end=<span class="string">' '</span>)</span><br><span class="line"> mostRight.right = <span class="literal">None</span></span><br><span class="line"> cur = cur.right</span><br></pre></td></tr></table></figure><br>Morris遍历的后序遍历有点麻烦,具体可以看参考文献</p>
<h3 id="测试及结果"><a href="#测试及结果" class="headerlink" title="测试及结果"></a>测试及结果</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line"> <span class="string">"""主函数"""</span></span><br><span class="line"> vals = <span class="built_in">range</span>(<span class="number">10</span>) <span class="comment"># 生成十个数据作为树节点</span></span><br><span class="line"> tree = Tree()</span><br><span class="line"> <span class="keyword">for</span> val <span class="keyword">in</span> vals:</span><br><span class="line"> tree.add(val)</span><br><span class="line"></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'队列实现层次遍历:'</span>)</span><br><span class="line"> <span class="built_in">print</span>(tree.level_queue(tree.root)) <span class="comment"># [[0], [1, 2], [3, 4, 5, 6], [7, 8, 9]]</span></span><br><span class="line"></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\n\n递归实现先序遍历:'</span>)</span><br><span class="line"> tree.front_recursive(tree.root) <span class="comment"># 0 1 3 7 8 4 9 2 5 6</span></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\n递归实现中序遍历:'</span>)</span><br><span class="line"> tree.middle_recursive(tree.root) <span class="comment"># 7 3 8 1 9 4 0 5 2 6</span></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\n递归实现后序遍历:'</span>)</span><br><span class="line"> tree.later_recursive(tree.root) <span class="comment"># 7 8 3 9 4 1 5 6 2 0</span></span><br><span class="line"></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\n\n堆栈实现先序遍历:'</span>)</span><br><span class="line"> tree.front_stack(tree.root) <span class="comment"># 0 1 3 7 8 4 9 2 5 6</span></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\n堆栈实现中序遍历:'</span>)</span><br><span class="line"> tree.middle_stack(tree.root) <span class="comment"># 7 3 8 1 9 4 0 5 2 6</span></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\n堆栈实现后序遍历:'</span>)</span><br><span class="line"> tree.later_stack(tree.root) <span class="comment"># 7 8 3 9 4 1 5 6 2 0</span></span><br><span class="line"></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\nMorris先序遍历:'</span>)</span><br><span class="line"> tree.morris(tree.root, <span class="string">'front'</span>) <span class="comment"># 0 1 3 7 8 4 9 2 5 6</span></span><br><span class="line"> <span class="built_in">print</span>(<span class="string">'\nMorris中序遍历:'</span>)</span><br><span class="line"> tree.morris(tree.root, <span class="string">'middle'</span>) <span class="comment"># 7 3 8 1 9 4 0 5 2 6</span></span><br></pre></td></tr></table></figure>
<h2 id="二叉搜索树"><a href="#二叉搜索树" class="headerlink" title="二叉搜索树"></a>二叉搜索树</h2><ul>
<li>简介:⼆叉搜索树(Binary Search Tree,BST)定义:⼀个⼆叉树中,任意节点的值要⼤于等于左⼦树所有节点的值,且要⼩于等于右边⼦树的所有节点的值。</li>
<li>性质:<ul>
<li>每个节点中的值必须大于或等于其左子树中的任何值</li>
<li>每个节点中的值必须小于或等于其右子树中的任何值</li>
<li>二叉搜索树<strong>中序遍历</strong>时,结果依此递增</li>
</ul>
</li>
</ul>
<h1 id="N叉树"><a href="#N叉树" class="headerlink" title="N叉树"></a>N叉树</h1><p>树的每个节点可以有两个以上的子节点,称为m阶的多叉树或m叉树</p>
<p><strong>节点实现</strong><br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span>:</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, val=<span class="literal">None</span>, children=<span class="literal">None</span></span>):</span></span><br><span class="line"> self.val = val</span><br><span class="line"> self.children = children</span><br></pre></td></tr></table></figure></p>
<h2 id="前缀树(字典树)"><a href="#前缀树(字典树)" class="headerlink" title="前缀树(字典树)"></a>前缀树(字典树)</h2><p>Trie,前缀树或字典树,是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。前缀树的节点可以是任意一个字符集中的字符,如对于都是小写字母的字符串,字符集就是’a’-‘z’;对于都是数字的字符串,字符集就是’0’-‘9’;对于二进制字符串,字符集就是0和1。前缀树有相当多的应用情景,例如自动补完和拼写检查。</p>
<p><strong>代码实现</strong><br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Trie</span>:</span></span><br><span class="line"> <span class="string">"""</span></span><br><span class="line"><span class="string"> 实现一个字符集为小写英文字母的前缀树</span></span><br><span class="line"><span class="string"> """</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self</span>):</span></span><br><span class="line"> <span class="string">"""</span></span><br><span class="line"><span class="string"> Initialize data structure.</span></span><br><span class="line"><span class="string"> """</span></span><br><span class="line"> self.children = [<span class="literal">None</span>] * <span class="number">26</span></span><br><span class="line"> self.isEnd = <span class="literal">False</span> <span class="comment"># 该节点是否是字符串的结尾</span></span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">searchPrefix</span>(<span class="params">self, prefix</span>):</span></span><br><span class="line"> <span class="string">"""</span></span><br><span class="line"><span class="string"> return None if prefix not in trie else the end of the prefix</span></span><br><span class="line"><span class="string"> """</span></span><br><span class="line"> node = self</span><br><span class="line"> <span class="keyword">for</span> ch <span class="keyword">in</span> prefix:</span><br><span class="line"> ch = <span class="built_in">ord</span>(ch) - <span class="built_in">ord</span>(<span class="string">'a'</span>)</span><br><span class="line"> <span class="keyword">if</span> <span class="keyword">not</span> node.children[ch]:</span><br><span class="line"> <span class="keyword">return</span> <span class="literal">None</span></span><br><span class="line"> node = node.children[ch]</span><br><span class="line"> <span class="keyword">return</span> node</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">insert</span>(<span class="params">self, word: <span class="built_in">str</span></span>) -> <span class="literal">None</span>:</span></span><br><span class="line"> <span class="string">"""</span></span><br><span class="line"><span class="string"> Inserts a word into the trie.</span></span><br><span class="line"><span class="string"> """</span></span><br><span class="line"> node = self</span><br><span class="line"> <span class="keyword">for</span> ch <span class="keyword">in</span> word:</span><br><span class="line"> ch = <span class="built_in">ord</span>(ch) - <span class="built_in">ord</span>(<span class="string">'a'</span>)</span><br><span class="line"> <span class="keyword">if</span> <span class="keyword">not</span> node.children[ch]:</span><br><span class="line"> <span class="comment"># 子节点不存在,创建一个新的子节点</span></span><br><span class="line"> node.children[ch] = Trie()</span><br><span class="line"> node = node.children[ch]</span><br><span class="line"> node.isEnd = <span class="literal">True</span></span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">search</span>(<span class="params">self, word: <span class="built_in">str</span></span>) -> <span class="built_in">bool</span>:</span></span><br><span class="line"> <span class="string">"""</span></span><br><span class="line"><span class="string"> Returns if the word is in the trie.</span></span><br><span class="line"><span class="string"> """</span></span><br><span class="line"> node = self.searchPrefix(word)</span><br><span class="line"> <span class="keyword">return</span> node <span class="keyword">is</span> <span class="keyword">not</span> <span class="literal">None</span> <span class="keyword">and</span> node.isEnd</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">startsWith</span>(<span class="params">self, prefix: <span class="built_in">str</span></span>) -> <span class="built_in">bool</span>:</span></span><br><span class="line"> <span class="string">"""</span></span><br><span class="line"><span class="string"> Returns if there is any word in the trie that starts with the given prefix.</span></span><br><span class="line"><span class="string"> """</span></span><br><span class="line"> <span class="keyword">return</span> self.searchPrefix(prefix) <span class="keyword">is</span> <span class="keyword">not</span> <span class="literal">None</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">'__main__'</span>:</span><br><span class="line"> trie = Trie()</span><br><span class="line"> trie.insert(<span class="string">"apple"</span>)</span><br><span class="line"> <span class="built_in">print</span>(trie.search(<span class="string">"apple"</span>)) <span class="comment"># True</span></span><br><span class="line"> <span class="built_in">print</span>(trie.search(<span class="string">"app"</span>)) <span class="comment"># False</span></span><br><span class="line"> <span class="built_in">print</span>(trie.startsWith(<span class="string">"app"</span>)) <span class="comment"># True</span></span><br><span class="line"> trie.insert(<span class="string">"app"</span>)</span><br><span class="line"> <span class="built_in">print</span>(trie.search(<span class="string">"app"</span>)) <span class="comment"># True</span></span><br></pre></td></tr></table></figure><br><strong>复杂度分析:</strong></p>
<ul>
<li>时间复杂度:<br>初始化为$O(1)$,其余操作为$O(|S|)$,$|S|$是每次插入或查询的字符串长度</li>
<li>空间复杂度:<br>$O(|T|·\Sigma)$,其中$|T|$为所有插入字符串的长度之和,$\Sigma$为字符集的大小,代码中$\Sigma=26$</li>
</ul>
<h1 id="其他特殊结构"><a href="#其他特殊结构" class="headerlink" title="其他特殊结构"></a>其他特殊结构</h1><ul>
<li>线段树</li>
<li>霍夫曼树</li>
<li>B树</li>
<li>红黑树</li>
</ul>
<h1 id="力扣指南"><a href="#力扣指南" class="headerlink" title="力扣指南"></a>力扣指南</h1><h1 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h1><ul>
<li><a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_30210107/article/details/88146252?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161182307616780274187603%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=161182307616780274187603&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v29-1-88146252.pc_search_result_hbase_insert&utm_term=二叉树的遍历迭代法python&spm=1018.2226.3001.4187">二叉树遍历和迭代方法</a></li>
<li><a target="_blank" rel="noopener" href="https://blog.csdn.net/heshiliqiu/article/details/111540928?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161183582816780271554041%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=161183582816780271554041&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~hot_rank-2-111540928.first_rank_v2_pc_rank_v29_10&utm_term=morris遍历&spm=1018.2226.3001.4187">Morris遍历的图示理解以及代码实现</a></li>
<li><a target="_blank" rel="noopener" href="https://blog.csdn.net/zearot/article/details/48299459?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163833033716780271977440%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163833033716780271977440&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-48299459.pc_search_all_es&utm_term=线段树&spm=1018.2226.3001.4187">线段树详解 (原理,实现与应用)</a></li>
</ul>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">Author: </span><span class="post-copyright-info"><a href="mailto:undefined">贪钱算法还我头发</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">Link: </span><span class="post-copyright-info"><a href="https://xfliu1998.github.io/2021/11/01/3-Tree/">https://xfliu1998.github.io/2021/11/01/3-Tree/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">Copyright Notice: </span><span class="post-copyright-info">All articles in this blog are licensed under <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a> unless stating additionally.</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a><a class="post-meta__tags" href="/tags/LeetCode/">LeetCode</a></div><div class="post_share"><div class="social-share" data-image="https://img.shijue.me/426930d8af0f4e2e924dd3c6bf8b2aaa_d.jpg!dp6" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2021/12/03/4-Smart-Search-and-Recommendation-System-Principles-Algorithm-and-Application/"><img class="prev-cover" src="https://img.shijue.me/bb6d4691be8e42359beedc6176c6f45e_d.jpeg!dp6" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">Previous Post</div><div class="prev_info">Smart Search and Recommendation System Principles, Algorithm and Application</div></div></a></div><div class="next-post pull-right"><a href="/2021/10/27/1-Ensemble-Learning/"><img class="next-cover" src="https://img.shijue.me/d0ad5b635947401e9e3d3633634e6811_d.jpg!dp6" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">Next Post</div><div class="next_info">Ensemble Learning</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>Related Articles</span></div><div class="relatedPosts-list"><div><a href="/2023/07/05/Number-Theory-and-Geometry/" title="Number Theory and Geometry"><img class="cover" src="https://img.shijue.me/d9a0b9ce22d44e6f9213e5ef8917385d_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-07-05</div><div class="title">Number Theory and Geometry</div></div></a></div><div><a href="/2023/06/13/Sort-Algorithm/" title="Sort Algorithm"><img class="cover" src="https://img.shijue.me/05adac4bd8b1447697e1053623e74d68_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-06-13</div><div class="title">Sort Algorithm</div></div></a></div><div><a href="/2023/06/04/Graph-Theory/" title="Graph Theory"><img class="cover" src="https://img.shijue.me/845aa0476235409e9ef646afb7c05ab7_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-06-04</div><div class="title">Graph Theory</div></div></a></div><div><a href="/2023/05/29/Divide-and-Conquer/" title="Divide and Conquer"><img class="cover" src="https://img.shijue.me/d5e5c8cc7dae431386f1d15c0006f217.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-05-29</div><div class="title">Divide and Conquer</div></div></a></div><div><a href="/2023/05/21/Greedy-Algorithm/" title="Greedy Algorithm"><img class="cover" src="https://img.shijue.me/73abae19e7ed4f279380e078361cafff_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-05-21</div><div class="title">Greedy Algorithm</div></div></a></div><div><a href="/2023/04/19/Dynamic-Programming/" title="Dynamic Programming"><img class="cover" src="https://img.shijue.me/eb9640e472e540b4bce2f24b9f11237d_d.jpg!dp6" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2023-04-19</div><div class="title">Dynamic Programming</div></div></a></div></div></div><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> Comment</span></div></div><div class="comment-wrap"><div><div id="gitalk-container"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="/images/head.jpg" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">贪钱算法还我头发</div><div class="author-info__description"></div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">Articles</div><div class="length-num">45</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">Tags</div><div class="length-num">12</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">Categories</div><div class="length-num">6</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="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/xfliu1998"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="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/xfliu1998" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="mailto:[email protected]" target="_blank" title="Email"><i class="fas fa-envelope"></i></a><a class="social-icon" href="https://blog.csdn.net/keiven_" target="_blank" title="CSDN"><i class="fa fa-address-card"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>Announcement</span></div><div class="announcement_content">欢迎来这里掉头发</div></div><div class="card-widget" id="newYear"><div class="item-headline"><i></i><span></span></div><div class="item-content"><div id="newYear-main"><div class="mask"></div> <p class="title"></p> <div class="newYear-time"></div> <p class="today" style="text-align: right;"></p> </div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>Catalog</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">1.</span> <span class="toc-text">二叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AE%9E%E7%8E%B0"><span class="toc-number">1.1.</span> <span class="toc-text">二叉树的实现</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86"><span class="toc-number">1.2.</span> <span class="toc-text">二叉树的遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%80%92%E5%BD%92%E6%B3%95"><span class="toc-number">1.2.1.</span> <span class="toc-text">递归法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%BF%AD%E4%BB%A3%E6%B3%95"><span class="toc-number">1.2.2.</span> <span class="toc-text">迭代法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Morris%E9%81%8D%E5%8E%86"><span class="toc-number">1.2.3.</span> <span class="toc-text">Morris遍历</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B5%8B%E8%AF%95%E5%8F%8A%E7%BB%93%E6%9E%9C"><span class="toc-number">1.2.4.</span> <span class="toc-text">测试及结果</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="toc-number">1.3.</span> <span class="toc-text">二叉搜索树</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#N%E5%8F%89%E6%A0%91"><span class="toc-number">2.</span> <span class="toc-text">N叉树</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E6%A0%91%EF%BC%88%E5%AD%97%E5%85%B8%E6%A0%91%EF%BC%89"><span class="toc-number">2.1.</span> <span class="toc-text">前缀树(字典树)</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%85%B6%E4%BB%96%E7%89%B9%E6%AE%8A%E7%BB%93%E6%9E%84"><span class="toc-number">3.</span> <span class="toc-text">其他特殊结构</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8A%9B%E6%89%A3%E6%8C%87%E5%8D%97"><span class="toc-number">4.</span> <span class="toc-text">力扣指南</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99"><span class="toc-number">5.</span> <span class="toc-text">参考资料</span></a></li></ol></div></div></div></div></main><footer id="footer" style="background-image: url('https://img.shijue.me/426930d8af0f4e2e924dd3c6bf8b2aaa_d.jpg!dp6')"><div id="footer-wrap"><div class="copyright">©2020 - 2024 <i id="heartbeat" class="fa fas fa-heartbeat"></i> 贪钱算法还我头发</div><div class="framework-info"><span>Framework </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>Theme </span><a target="_blank" rel="noopener" href="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/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div><head><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/HCLonely/images@master/others/heartbeat.min.css"></head></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="Read Mode"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="Switch Between Light And Dark Mode"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="Toggle between single-column and double-column"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="Setting"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="Table Of Contents"><i class="fas fa-list-ul"></i></button><a id="to_comment" href="#post-comment" title="Scroll To Comments"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="Back To Top"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><div class="search-dialog__title" id="local-search-title">Local search</div><div id="local-input-panel"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="Search for Posts" type="text"/></div></div></div><hr/><div id="local-search-results"></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
window.MathJax = {
tex: {
inlineMath: [ ['$','$'], ["\\(","\\)"]],
tags: 'ams'
},
chtml: {
scale: 1.2
},
options: {
renderActions: {
findScript: [10, doc => {
for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
const display = !!node.type.match(/; *mode=display/)
const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
const text = document.createTextNode('')
node.parentNode.replaceChild(text, node)
math.start = {node: text, delim: '', n: 0}
math.end = {node: text, delim: '', n: 0}
doc.math.push(math)
}
}, ''],
insertScript: [200, () => {
document.querySelectorAll('mjx-container:not\([display]\)').forEach(node => {
const target = node.parentNode
if (target.nodeName.toLowerCase() === 'li') {
target.parentNode.classList.add('has-jax')
} else {
target.classList.add('has-jax')
}
});
}, '', false]
}
}
}
const script = document.createElement('script')
script.src = 'https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js'
script.id = 'MathJax-script'
script.async = true
document.head.appendChild(script)
} else {
MathJax.startup.document.state(0)
MathJax.texReset()
MathJax.typeset()
}</script><script>function addGitalkSource () {
const ele = document.createElement('link')
ele.rel = 'stylesheet'
ele.href= 'https://cdn.jsdelivr.net/npm/gitalk/dist/gitalk.min.css'
document.getElementsByTagName('head')[0].appendChild(ele)
}
function loadGitalk () {
function initGitalk () {
var gitalk = new Gitalk(Object.assign({
clientID: '1b0c10ce649501ea4a72',
clientSecret: '741b5e861137e3d5a482bba272c8201b78da6cb0',
repo: 'xfliu1998.github.io',
owner: 'xfliu1998',
admin: ['xfliu1998'],
id: '67b131b894129e94d62d6692a480992d',
language: 'en',
perPage: 10,
distractionFreeMode: false,
pagerDirection: 'last',
createIssueManually: true,
updateCountCallback: commentCount
},null))
gitalk.render('gitalk-container')
}
if (typeof Gitalk === 'function') initGitalk()
else {
addGitalkSource()
getScript('https://cdn.jsdelivr.net/npm/gitalk@latest/dist/gitalk.min.js').then(initGitalk)
}
}
function commentCount(n){
let isCommentCount = document.querySelector('#post-meta .gitalk-comment-count')
if (isCommentCount) {
isCommentCount.innerHTML= n
}
}
if ('Gitalk' === 'Gitalk' || !false) {
if (false) btf.loadComment(document.getElementById('gitalk-container'), loadGitalk)
else loadGitalk()
} else {
function loadOtherComment () {
loadGitalk()
}
}</script></div><script src="/js/script.js?v1"></script><script src="https://cdn.staticfile.org/jquery/3.6.3/jquery.min.js"></script><script async data-pjax src="https://cdn.wpon.cn/2022-sucai/Gold-ingot.js"></script><script async data-pjax src="/js/newYear.js"></script><script async src="//at.alicdn.com/t/font_2264842_b004iy0kk2b.js"></script><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/activate-power-mode.min.js"></script><script>POWERMODE.colorful = true;
POWERMODE.shake = true;
POWERMODE.mobile = false;
document.body.addEventListener('input', POWERMODE);
</script><script id="click-heart" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/click-heart.min.js" async="async" mobile="false"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><!-- hexo injector body_end start --> <script data-pjax>if(document.getElementById('recent-posts') && (location.pathname ==='all'|| 'all' ==='all')){
var parent = document.getElementById('recent-posts');
var child = '<div class="recent-post-item" style="width:100%;height: auto"><div id="catalog_magnet"><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Machine-Learning-and-Deep-Learning/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">👩💻 机器学习与深度学习 (6)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Data-Structures-and-Algorithms/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">😼 数据结构与算法 (16)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Search-Advertisement-Recommendation-Causal/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">🗂️ 搜索/广告/推荐/因果 (10)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Data-Analysis-and-Processing/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">📒 数据分析与处理 (4)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Reading-Notes/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">📚 阅读笔记 (6)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><div class="magnet_item"><a class="magnet_link" href="https://xfliu1998.github.io/categories/Daily/"><div class="magnet_link_context" style=""><span style="font-weight:500;flex:1">💡 日常随想 (3)</span><span style="padding:0px 4px;border-radius: 8px;"><i class="fas fa-arrow-circle-right"></i></span></div></a></div><a class="magnet_link_more" href="https://xfliu1998.github.io/categories" style="flex:1;text-align: center;margin-bottom: 10px;">查看更多...</a></div></div>';
console.log('已挂载magnet')
parent.insertAdjacentHTML("afterbegin",child)}
</script><style>#catalog_magnet{flex-wrap: wrap;display: flex;width:100%;justify-content:space-between;padding: 10px 10px 0 10px;align-content: flex-start;}.magnet_item{flex-basis: calc(50% - 5px);background: #f2f2f2;margin-bottom: 10px;border-radius: 8px;transition: all 0.2s ease-in-out;}.magnet_item:hover{background: #b30070}.magnet_link_more{color:#555}.magnet_link{color:black}.magnet_link:hover{color:white}@media screen and (max-width: 600px) {.magnet_item {flex-basis: 100%;}}.magnet_link_context{display:flex;padding: 10px;font-size:16px;transition: all 0.2s ease-in-out;}.magnet_link_context:hover{padding: 10px 20px;}</style>
<style></style><script data-pjax>
function butterfly_swiper_injector_config(){
var parent_div_git = document.getElementById('recent-posts');
var item_html = '<div class="recent-post-item" style="height: auto;width: 100%"><div class="blog-slider swiper-container-fade swiper-container-horizontal" id="swiper_container"><div class="blog-slider__wrp swiper-wrapper" style="transition-duration: 0ms;"><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/09/17/Papers-Reading-about-NLP/" alt=""><img width="48" height="48" src="https://tse1-mm.cn.bing.net/th/id/OIP-C.KNjcp6IetyzFaIaSc8-eKAHaE8?w=303&h=201&c=7&r=0&o=5&dpr=1.88&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-09-17</span><a class="blog-slider__title" href="2022/09/17/Papers-Reading-about-NLP/" alt="">Papers Reading about NLP</a><div class="blog-slider__text">自然语言处理论文阅读笔记</div><a class="blog-slider__button" href="2022/09/17/Papers-Reading-about-NLP/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/10/01/9-3D-Construction/" alt=""><img width="48" height="48" src="https://img.zcool.cn/community/017d495d0e6a9ea801205e4b7fa13c.png@1280w_1l_2o_100sh.png" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-10-01</span><a class="blog-slider__title" href="2022/10/01/9-3D-Construction/" alt="">3D Construction</a><div class="blog-slider__text">三维重建基础</div><a class="blog-slider__button" href="2022/10/01/9-3D-Construction/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2023/01/11/SfM-SLAM/" alt=""><img width="48" height="48" src="https://tse2-mm.cn.bing.net/th/id/OIP-C.V5uTTQ6LTBHc42xoBPG8hAHaEm?pid=ImgDet&rs=1" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-01-11</span><a class="blog-slider__title" href="2023/01/11/SfM-SLAM/" alt="">SfM & SLAM</a><div class="blog-slider__text">SfM和SLAM系统</div><a class="blog-slider__button" href="2023/01/11/SfM-SLAM/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2023/03/25/Papers-Ideas/" alt=""><img width="48" height="48" src="https://tse2-mm.cn.bing.net/th/id/OIP-C.Mmv8iGEVFxSQII6QH0BG9QHaEJ?w=302&h=180&c=7&r=0&o=5&dpr=2&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-03-25</span><a class="blog-slider__title" href="2023/03/25/Papers-Ideas/" alt="">Papers Ideas</a><div class="blog-slider__text">大模型时代下的科研思路</div><a class="blog-slider__button" href="2023/03/25/Papers-Ideas/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/09/17/Papers-Summary/" alt=""><img width="48" height="48" src="https://tse1-mm.cn.bing.net/th/id/OIP-C.KNjcp6IetyzFaIaSc8-eKAHaE8?w=303&h=201&c=7&r=0&o=5&dpr=1.88&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-09-17</span><a class="blog-slider__title" href="2022/09/17/Papers-Summary/" alt="">Papers Summary</a><div class="blog-slider__text">论文总结笔记</div><a class="blog-slider__button" href="2022/09/17/Papers-Summary/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/09/17/Papers-Reading-about-CV/" alt=""><img width="48" height="48" src="https://tse1-mm.cn.bing.net/th/id/OIP-C.KNjcp6IetyzFaIaSc8-eKAHaE8?w=303&h=201&c=7&r=0&o=5&dpr=1.88&pid=1.7" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-09-17</span><a class="blog-slider__title" href="2022/09/17/Papers-Reading-about-CV/" alt="">Papers Reading about CV</a><div class="blog-slider__text">计算机视觉论文阅读笔记</div><a class="blog-slider__button" href="2022/09/17/Papers-Reading-about-CV/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2023/06/05/Interview-Experience/" alt=""><img width="48" height="48" src="https://img.shijue.me/00964c481ad34d78acbf148d2b391c9e_d.jpg!dp6" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2023-06-05</span><a class="blog-slider__title" href="2023/06/05/Interview-Experience/" alt="">Interview Experience</a><div class="blog-slider__text">面经八股</div><a class="blog-slider__button" href="2023/06/05/Interview-Experience/" alt="">详情 </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/01/21/Learning-Framework/" alt=""><img width="48" height="48" src="https://img.shijue.me/78ae8b05a73444cd9643a8312abc0d43.jpg!dp6" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-01-21</span><a class="blog-slider__title" href="2022/01/21/Learning-Framework/" alt="">Learning Framework</a><div class="blog-slider__text">学习大纲</div><a class="blog-slider__button" href="2022/01/21/Learning-Framework/" alt="">详情 </a></div></div></div><div class="blog-slider__pagination swiper-pagination-clickable swiper-pagination-bullets"></div></div></div>';
console.log('已挂载butterfly_swiper')
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
}
var elist = 'undefined'.split(',');
var cpage = location.pathname;
var epage = '/';
var flag = 0;
for (var i=0;i<elist.length;i++){
if (cpage.includes(elist[i])){
flag++;
}
}
if ((epage ==='all')&&(flag == 0)){
butterfly_swiper_injector_config();
}
else if (epage === cpage){
butterfly_swiper_injector_config();
}
</script><script defer src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.js"></script><script defer data-pjax src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper_init.js"></script><script data-pjax src="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.js"></script><script data-pjax>
function gitcalendar_injector_config(){
var parent_div_git = document.getElementById('recent-posts');
var item_html = '<container><style>#git_container{min-height: 280px}@media screen and (max-width:650px) {#git_container{min-height: 0px}}</style><div id="git_loading" style="width:10%;height:100%;margin:0 auto;display: block;"><svg xmlns="https://www.w3.org/2000/svg" xmlns:xlink="https://www.w3.org/1999/xlink" viewBox="0 0 50 50" style="enable-background:new 0 0 50 50" xml:space="preserve"><path fill="#d0d0d0" d="M25.251,6.461c-10.318,0-18.683,8.365-18.683,18.683h4.068c0-8.071,6.543-14.615,14.615-14.615V6.461z" transform="rotate(275.098 25 25)"><animatetransform attributeType="xml" attributeName="transform" type="rotate" from="0 25 25" to="360 25 25" dur="0.6s" repeatCount="indefinite"></animatetransform></path></svg><style>#git_container{display: none;}</style></div><div id="git_container"></div></container>';
parent_div_git.insertAdjacentHTML("afterbegin",item_html)
console.log('已挂载gitcalendar')
}
if( document.getElementById('recent-posts') && (location.pathname ==='/'|| '/' ==='all')){
gitcalendar_injector_config()
GitCalendarInit("https://gitcalendar.fomal.cc/api?xfliu1998",['#d9e0df', '#c6e0dc', '#a8dcd4', '#9adcd2', '#89ded1', '#77e0d0', '#5fdecb', '#47dcc6', '#39dcc3', '#1fdabe', '#00dab9'],'xfliu1998')
}
</script><!-- hexo injector body_end end --><script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"model":{"jsonPath":"/live2dw/assets/haruto.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"log":false,"pluginJsPath":"lib/","pluginModelPath":"assets/","pluginRootPath":"live2dw/","tagMode":false});</script></body></html>