資訊專欄INFORMATION COLUMN
摘要：關(guān)于二叉樹(shù)的遍歷，使用棧遞歸或者仿棧循環(huán)都是需要的空間，保證了空間為，時(shí)間還是比原來(lái)多了一遍。思路對(duì)每一個(gè)節(jié)點(diǎn)，優(yōu)先找到一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)的作用是，當(dāng)后續(xù)節(jié)點(diǎn)遍歷到這個(gè)位置時(shí)，可以直接通過(guò)這個(gè)節(jié)點(diǎn)返回它需要返回的位置。
關(guān)于二叉樹(shù)的遍歷，使用棧遞歸或者仿棧循環(huán)都是需要O(N)的空間，Morris Traversal保證了空間為O(1)，時(shí)間還是O(N)（比原來(lái)多了一遍）。
這里只介紹inOrder順序。
思路：
對(duì)每一個(gè)cur節(jié)點(diǎn)，優(yōu)先找到一個(gè)pre節(jié)點(diǎn)，這個(gè)pre節(jié)點(diǎn)的作用是，當(dāng)后續(xù)cur節(jié)點(diǎn)遍歷 到這個(gè)位置時(shí)，可以直接通過(guò)這個(gè)pre節(jié)點(diǎn)返回它需要返回的位置。
例如：
6
/
4 8
/
2 5
上面當(dāng)cur節(jié)點(diǎn)在6的時(shí)候，pre節(jié)點(diǎn)會(huì)在5，因?yàn)楹竺娈?dāng)cur節(jié)點(diǎn)遍歷到5的時(shí)候，可以通過(guò)pre節(jié)點(diǎn)直接返回6
當(dāng)cur節(jié)點(diǎn)再4的時(shí)候，pre節(jié)點(diǎn)會(huì)在2，當(dāng)后面cur到2的時(shí)候，可以直接返回4
pre找到了，是通過(guò)什么返回呢，因?yàn)椴荒苄薷亩鏄?shù)結(jié)構(gòu)，也不能使用堆棧記錄。
通過(guò)mirror(鏡像)，也就是說(shuō)，當(dāng)找到pre的時(shí)候（每個(gè)pre的右節(jié)點(diǎn)確保為null），在它的右節(jié)點(diǎn)創(chuàng)建一個(gè)鏡像節(jié)點(diǎn)，
這個(gè)鏡像節(jié)點(diǎn)直接指向當(dāng)前的cur節(jié)點(diǎn)。
這個(gè)操作是不占用空間的，因?yàn)橹皇腔ハ嘁谩?/p>
例如：當(dāng)上面的cur為6，pre為5，那么設(shè)置pre.right=cur，感覺(jué)上是這樣：
6
/
4 8
/
2 5
6
/
4 8
...
其實(shí)并沒(méi)有多出來(lái)那一塊，只是5引用到6罷了
6
/ ↑
4 ↑ 8
/ ↑
2 5
理解了這些，那么后續(xù)就簡(jiǎn)單了，當(dāng)cur遍歷到pre的時(shí)候并且打印后，將pre新增的引用刪除恢復(fù)原來(lái)的樹(shù)便可。
代碼：
function morrisTraversal(root){
let cur=root,pre
while(cur!=null){
// 當(dāng)左為空，直接打印
if(cur.left==null){
console.log(cur.val)
cur=cur.right
}else{
// 當(dāng)左不為空，先去找 pre
pre=cur.left
while(pre.right!=null && pre.right!==cur){
pre=pre.right
}
// 建立引用，用于返回
if(pre.right==null){
pre.right=cur
cur=cur.left
}else{
// 刪除引用
console.log(cur.val)
pre.right=null
cur=cur.right
}
}
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/100846.html
摘要：樹(shù)和樹(shù)的算法一樹(shù)樹(shù)的概念樹(shù)英語(yǔ)是一種抽象數(shù)據(jù)類型或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時(shí)間復(fù)雜度額外空間復(fù)雜度的二叉樹(shù)的遍歷方式，為二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。 樹(shù)和樹(shù)的算法 一、樹(shù) 1.1 樹(shù)的概念 樹(shù)（英語(yǔ)：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)...
摘要：樹(shù)和樹(shù)的算法一樹(shù)樹(shù)的概念樹(shù)英語(yǔ)是一種抽象數(shù)據(jù)類型或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時(shí)間復(fù)雜度額外空間復(fù)雜度的二叉樹(shù)的遍歷方式，為二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。 樹(shù)和樹(shù)的算法 一、樹(shù) 1.1 樹(shù)的概念 樹(shù)（英語(yǔ)：tree）是一種抽象數(shù)據(jù)類型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>=1）個(gè)有限節(jié)點(diǎn)組成一個(gè)...
摘要：遞歸解法由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法前序遍歷遞歸遞歸中序遍歷遞歸遞歸后序遍歷遞歸遞歸三種遞歸遍歷的總結(jié)遞歸終止的條件為碰到空節(jié)點(diǎn)。 目錄 分析二叉樹(shù)的前序，中序，后序的遍歷步驟 1.層序遍歷 方法一：廣度優(yōu)先搜索? (以下解釋來(lái)自leetcode官方題解) 方法...
摘要：解法一中序遍歷分析由于給定了二叉搜索樹(shù)，因此首先考慮中序遍歷，使用示例，我們先來(lái)分別看一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果二叉搜索樹(shù)二叉累加樹(shù)。這里還是使用示例，我們?cè)賮?lái)觀察一下二叉搜索樹(shù)和累加樹(shù)中序遍歷的結(jié)果二叉搜索樹(shù)二叉累加樹(shù)。 ...
摘要：一個(gè)二叉樹(shù)的例子廣度優(yōu)先遍歷廣度優(yōu)先遍歷是從二叉樹(shù)的第一層根結(jié)點(diǎn)開(kāi)始，自上至下逐層遍歷在同一層中，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問(wèn)。有的書(shū)里將二叉樹(shù)的遍歷只講了上面三種遞歸遍歷。 二叉樹(shù)是由根節(jié)點(diǎn)，左子樹(shù)，右子樹(shù)組成，左子樹(shù)和友子樹(shù)分別是一個(gè)二叉樹(shù)。這篇文章主要在JS中實(shí)現(xiàn)二叉樹(shù)的遍歷。 一個(gè)二叉樹(shù)的例子 var tree = { value: 1, left: { ...
閱讀 1242·2021-11-23 10:10
閱讀 1648·2021-09-30 09:47
閱讀 982·2021-09-27 14:02
閱讀 3044·2019-08-30 15:45
閱讀 3086·2019-08-30 14:11
閱讀 3680·2019-08-29 14:05
閱讀 1880·2019-08-29 13:51
閱讀 2267·2019-08-29 11:33
