0
  • 聊天消息
  • 系統(tǒng)消息
  • 評(píng)論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫(xiě)文章/發(fā)帖/加入社區(qū)
會(huì)員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識(shí)你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

二叉樹(shù)的前序遍歷非遞歸實(shí)現(xiàn)

算法與數(shù)據(jù)結(jié)構(gòu) ? 來(lái)源:袁廚的算法小屋 ? 作者:袁廚的算法小屋 ? 2021-05-28 13:59 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

我們之前說(shuō)了二叉樹(shù)基礎(chǔ)及二叉的幾種遍歷方式及練習(xí)題,今天我們來(lái)看一下二叉樹(shù)的前序遍歷非遞歸實(shí)現(xiàn)。

前序遍歷的順序是, 對(duì)于樹(shù)中的某節(jié)點(diǎn),先遍歷該節(jié)點(diǎn),然后再遍歷其左子樹(shù),最后遍歷其右子樹(shù)。

我們先來(lái)通過(guò)下面這個(gè)動(dòng)畫(huà)復(fù)習(xí)一下二叉樹(shù)的前序遍歷。

迭代遍歷

我們?cè)囅胍幌?,之前我們借助?duì)列幫我們實(shí)現(xiàn)二叉樹(shù)的層序遍歷,

那么可不可以,也借助數(shù)據(jù)結(jié)構(gòu),幫助我們實(shí)現(xiàn)二叉樹(shù)的前序遍歷。

假設(shè)我們的二叉樹(shù)為 [1,2,3]。我們需要對(duì)其進(jìn)行前序遍歷。其遍歷順序?yàn)?/p>

當(dāng)前節(jié)點(diǎn) 1,左孩子 2,右孩子 3。

這里可不可以用棧,幫我們完成前序遍歷呢?

棧和隊(duì)列的那些事

我們都知道棧的特性是先進(jìn)后出,我們借助棧來(lái)幫助我們完成前序遍歷的時(shí)候。

則需要注意的一點(diǎn)是,我們應(yīng)該先將右子節(jié)點(diǎn)入棧,再將左子節(jié)點(diǎn)入棧。

這樣出棧時(shí),則會(huì)先出左節(jié)點(diǎn),再出右子節(jié)點(diǎn),則能夠完成樹(shù)的前序遍歷。

我們用一句話對(duì)上圖進(jìn)行總結(jié),當(dāng)棧不為空時(shí),棧頂元素出棧,如果其右孩子不為空,則右孩子入棧,其左孩子不為空,則左孩子入棧。還有一點(diǎn)需要注意的是,我們和層序遍歷一樣,需要先將 root 節(jié)點(diǎn)進(jìn)行入棧,然后再執(zhí)行 while 循環(huán)。

看到這里你已經(jīng)能夠自己編寫(xiě)出代碼了,不信你去試試。

時(shí)間復(fù)雜度:O(n) 需要對(duì)所有節(jié)點(diǎn)遍歷一次

空間復(fù)雜度:O(n) 棧的開(kāi)銷(xiāo),平均為 O(logn) 最快情況,即斜二叉樹(shù)時(shí)為 O(n)

參考代碼

class Solution {

public List《Integer》 preorderTraversal(TreeNode root) {

List《Integer》 list = new ArrayList《》();

Stack《TreeNode》 stack = new Stack《》();

if (root == null) return list;

stack.push(root);

while (!stack.isEmpty()) {

TreeNode temp = stack.pop();

if (temp.right != null) {

stack.push(temp.right);

}

if (temp.left != null) {

stack.push(temp.left);

}

//這里也可以放到前面

list.add(temp.val);

}

return list;

}

}

Morris

Morris 遍歷利用樹(shù)的左右孩子為空(大量空閑指針),實(shí)現(xiàn)空間開(kāi)銷(xiāo)的極限縮減。這個(gè)遍歷方式,稍微有那么一丟丟難理解,不過(guò)結(jié)合動(dòng)圖,也就一目了然,下面我們先看動(dòng)畫(huà)吧。

看完視頻,是不是感覺(jué)自己搞懂了,又感覺(jué)自己沒(méi)搞懂,哈哈,咱們繼續(xù)往下看。

我們之前說(shuō)的,Morris 遍歷利用了樹(shù)中大量空閑指針的特性,我們需要找到當(dāng)前節(jié)點(diǎn)的左子樹(shù)中的最右邊的葉子節(jié)點(diǎn),將該葉子節(jié)點(diǎn)的 right 指向當(dāng)前節(jié)點(diǎn)。例如當(dāng)前節(jié)點(diǎn)為2,其左子樹(shù)中的最右節(jié)點(diǎn)為 9 ,則在 9 節(jié)點(diǎn)添加一個(gè) right 指針指向 2。

其實(shí)上圖中的 Morris 遍歷遵循兩個(gè)原則,我們?cè)趧?dòng)畫(huà)中也能夠得出。

1.當(dāng) p1.left == null 時(shí),p1 = p1.right。(這也就是我們?yōu)槭裁匆o葉子節(jié)點(diǎn)添加 right 指針的原因)

2.如果 p1.left != null,找到 p1 左子樹(shù)上最右的節(jié)點(diǎn)。(也就是我們的 p2 最后停留的位置),此時(shí)我們又可以分為兩種情況,一種是葉子節(jié)點(diǎn)添加 right 指針的情況,一種是去除葉子節(jié)點(diǎn) right 指針的情況。

如果 p2 的 right 指針指向空,讓其指向 p1,p1向左移動(dòng),即 p1 = p1.left

如果 p2 的 right 指針指向 p1,讓其指向空,(為了防止重復(fù)執(zhí)行,則需要去掉 right 指針)p1 向右移動(dòng),p1 = p1.right。

這時(shí)你可以結(jié)合咱們剛才提到的兩個(gè)原則,再去看一遍動(dòng)畫(huà),并代入規(guī)則進(jìn)行模擬,差不多就能完全搞懂啦。

下面我們來(lái)對(duì)動(dòng)畫(huà)中的內(nèi)容進(jìn)行拆解 ,

首先 p1 指向 root節(jié)點(diǎn)

p2 = p1.left,下面我們需要通過(guò) p2 找到 p1的左子樹(shù)中的最右節(jié)點(diǎn)。即節(jié)點(diǎn) 5,然后將該節(jié)點(diǎn)的 right 指針指向 root。并記錄 root 節(jié)點(diǎn)的值。

向左移動(dòng) p1,即 p1 = p1.left

p2 = p1.left ,即節(jié)點(diǎn) 4 ,找到 p1 的左子樹(shù)中的最右葉子節(jié)點(diǎn),也就是 9,并將該節(jié)點(diǎn)的 right 指針指向 2。

繼續(xù)向左移動(dòng) p1,即 p1 = p1.left,p2 = p1.left。也就是節(jié)點(diǎn) 8。并將該節(jié)點(diǎn)的 right 指針指向 p1。

我們發(fā)現(xiàn)這一步給前兩步是一樣的,都是找到葉子節(jié)點(diǎn),將其 right 指針指向 p1,此時(shí)我們完成了添加 right 指針的過(guò)程,下面我們繼續(xù)往下看。

我們繼續(xù)移動(dòng) p1 指針,p1 = p1.left。p2 = p.left。此時(shí)我們發(fā)現(xiàn) p2 == null,即下圖此時(shí)我們需要移動(dòng) p1, 但是不再是 p1 = p1.left 而是 p1 = p1.right。也就是 4,繼續(xù)讓 p2 = p1.left。此時(shí)則為下圖這種情況

此時(shí)我們發(fā)現(xiàn) p2.right != null 而是指向 4,說(shuō)明此時(shí)我們已經(jīng)添加過(guò)了 right 指針,所以去掉 right 指針,并讓 p1 = p1.right

下面則繼續(xù)移動(dòng) p1 ,按照規(guī)則繼續(xù)移動(dòng)即可,遇到的情況已經(jīng)在上面做出了舉例,所以下面我們就不繼續(xù)贅述啦,如果還不是特別理解的同學(xué),可以再去看一遍動(dòng)畫(huà)加深下印象。時(shí)間復(fù)雜度 O(n),空間復(fù)雜度 O(1)下面我們來(lái)看代碼吧。

代碼

class Solution {

public List《Integer》 preorderTraversal(TreeNode root) {

List《Integer》 list = new ArrayList《》();

if (root == null) {

return list;

}

TreeNode p1 = root; TreeNode p2 = null;

while (p1 != null) {

p2 = p1.left;

if (p2 != null) {

//找到左子樹(shù)的最右葉子節(jié)點(diǎn)

while (p2.right != null && p2.right != p1) {

p2 = p2.right;

}

//添加 right 指針,對(duì)應(yīng) right 指針為 null 的情況

if (p2.right == null) {

list.add(p1.val);

p2.right = p1;

p1 = p1.left;

continue;

}

//對(duì)應(yīng) right 指針存在的情況,則去掉 right 指針

p2.right = null;

} else {

list.add(p1.val);

}

//移動(dòng) p1

p1 = p1.right;

}

return list;

}

}

原文標(biāo)題:把二叉樹(shù)揉碎(二)

文章出處:【微信公眾號(hào):算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯:haq

聲明:本文內(nèi)容及配圖由入駐作者撰寫(xiě)或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點(diǎn)僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場(chǎng)。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問(wèn)題,請(qǐng)聯(lián)系本站處理。 舉報(bào)投訴
  • 二叉樹(shù)
    +關(guān)注

    關(guān)注

    0

    文章

    74

    瀏覽量

    12604

原文標(biāo)題:把二叉樹(shù)揉碎(二)

文章出處:【微信號(hào):TheAlgorithm,微信公眾號(hào):算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。

收藏 0人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評(píng)論

    相關(guān)推薦
    熱點(diǎn)推薦

    想在rtsmart中使用uart2,是不是只能通過(guò)修改設(shè)備樹(shù)方法來(lái)實(shí)現(xiàn)uart2的復(fù)用呀?

    我想在rtsmart中使用uart2,是不是只能通過(guò)修改設(shè)備樹(shù)方法來(lái)實(shí)現(xiàn)uart2的復(fù)用呀? 修改設(shè)備樹(shù)后如何只編譯設(shè)備樹(shù)文件? 編譯生成的文件可以直接替換到廬山派里嗎,具體替換路徑在
    發(fā)表于 06-24 07:04

    嵌入式學(xué)習(xí)-飛凌嵌入式ElfBoard ELF 1板卡-初識(shí)設(shè)備樹(shù)之設(shè)備樹(shù)組成和結(jié)構(gòu)

    的name和value。在設(shè)備樹(shù)中,可描述的信息包括:一、CPU的數(shù)量和類(lèi)別;、內(nèi)存基地址和大??;三、總線和橋;四、外設(shè)連接;五、中斷控制器和中斷使用情況;六、GPIO控制器和GPIO使用情況;七
    發(fā)表于 01-08 08:32

    字符串反轉(zhuǎn)的實(shí)現(xiàn)方式

    在編程中,字符串反轉(zhuǎn)是一個(gè)基礎(chǔ)而重要的操作,它涉及到將一個(gè)字符串中的字符順序顛倒過(guò)來(lái)。這個(gè)操作在多種編程語(yǔ)言中都有不同的實(shí)現(xiàn)方式,本文將探討幾種常見(jiàn)的字符串反轉(zhuǎn)方法。 1. 遞歸方法 遞歸是一種通過(guò)
    的頭像 發(fā)表于 01-07 15:27 ?794次閱讀

    飛凌嵌入式ElfBoard ELF 1板卡-初識(shí)設(shè)備樹(shù)之設(shè)備樹(shù)組成和結(jié)構(gòu)

    的name和value。在設(shè)備樹(shù)中,可描述的信息包括:一、CPU的數(shù)量和類(lèi)別;、內(nèi)存基地址和大??;三、總線和橋;四、外設(shè)連接;五、中斷控制器和中斷使用情況;六、GPIO控制器和GPIO使用情況;七
    發(fā)表于 01-07 09:16

    什么是默克爾樹(shù)(Merkle Tree)?如何計(jì)算默克爾根?

    01 默克爾樹(shù)的概念 默克爾樹(shù)(Merkle Tree)是一種特殊的二叉樹(shù),它的每個(gè)節(jié)點(diǎn)都存儲(chǔ)了一個(gè)數(shù)據(jù)塊的哈希值。哈希值是一種可以將任意長(zhǎng)度的數(shù)據(jù)轉(zhuǎn)換為固定長(zhǎng)度的字符串的算法,它具有唯一性和不可
    的頭像 發(fā)表于 09-30 18:22 ?2203次閱讀
    什么是默克爾<b class='flag-5'>樹(shù)</b>(Merkle Tree)?如何計(jì)算默克爾根?

    【北京迅為】iTOP-i.MX6開(kāi)發(fā)板使用手冊(cè)第四部分固件編譯第十四章設(shè)備樹(shù)Android4.4系統(tǒng)編譯

    【北京迅為】iTOP-i.MX6開(kāi)發(fā)板使用手冊(cè)第四部分固件編譯第十四章設(shè)備樹(shù)Android4.4系統(tǒng)編譯
    的頭像 發(fā)表于 09-12 15:43 ?888次閱讀
    【北京迅為】iTOP-i.MX6開(kāi)發(fā)板使用手冊(cè)第四部分固件編譯第十四章<b class='flag-5'>非</b>設(shè)備<b class='flag-5'>樹(shù)</b>Android4.4系統(tǒng)編譯

    Python遞歸的經(jīng)典案例

    當(dāng)我們碰到諸如需要求階乘或斐波那契數(shù)列的問(wèn)題時(shí),使用普通的循環(huán)往往比較麻煩,但如果我們使用遞歸時(shí),會(huì)簡(jiǎn)單許多,起到事半功倍的效果。這篇文章主要和大家分享一些和遞歸有關(guān)的經(jīng)典案例,結(jié)合一些資料談一下個(gè)人的理解,也借此加深自己對(duì)遞歸
    的頭像 發(fā)表于 08-05 15:57 ?699次閱讀

    遞歸神經(jīng)網(wǎng)絡(luò)和循環(huán)神經(jīng)網(wǎng)絡(luò)的模型結(jié)構(gòu)

    遞歸神經(jīng)網(wǎng)絡(luò)是一種旨在處理分層結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò),使其特別適合涉及樹(shù)狀或嵌套數(shù)據(jù)的任務(wù)。這些網(wǎng)絡(luò)明確地模擬了層次結(jié)構(gòu)中的關(guān)系和依賴(lài)關(guān)系,例如語(yǔ)言中的句法結(jié)構(gòu)或圖像中的層次表示。它使用遞歸操作來(lái)分層處理信息,有效地捕獲上下文信息。
    的頭像 發(fā)表于 07-10 17:21 ?1241次閱讀
    <b class='flag-5'>遞歸</b>神經(jīng)網(wǎng)絡(luò)和循環(huán)神經(jīng)網(wǎng)絡(luò)的模型結(jié)構(gòu)

    遞歸神經(jīng)網(wǎng)絡(luò)的實(shí)現(xiàn)方法

    (Recurrent Neural Network,通常也簡(jiǎn)稱(chēng)為RNN,但在此處為區(qū)分,我們將循環(huán)神經(jīng)網(wǎng)絡(luò)稱(chēng)為Recurrent RNN)不同,遞歸神經(jīng)網(wǎng)絡(luò)更側(cè)重于處理樹(shù)狀或圖結(jié)構(gòu)的數(shù)據(jù),如句法分析樹(shù)、自然語(yǔ)言的語(yǔ)法結(jié)構(gòu)等。以下將從遞歸
    的頭像 發(fā)表于 07-10 17:02 ?758次閱讀

    指電極上覆蓋敏感材料的阻值計(jì)算

    覆蓋的敏感材料厚度超出指厚度時(shí)計(jì)算電阻,是否可以視作指電極指間電阻多個(gè)周期串聯(lián)后與超出指厚度部分敏感材料電阻并聯(lián)
    發(fā)表于 07-05 14:48

    遞歸神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)形式主要分為

    結(jié)構(gòu)形式。 Elman網(wǎng)絡(luò) Elman網(wǎng)絡(luò)是一種基本的遞歸神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu),由Elman于1990年提出。其結(jié)構(gòu)主要包括輸入層、隱藏層和輸出層,其中隱藏層具有時(shí)間延遲單元,可以存儲(chǔ)前一時(shí)刻的隱藏狀態(tài)。Elman網(wǎng)絡(luò)的基本原理是將前一時(shí)刻的隱藏狀態(tài)作為當(dāng)前時(shí)刻的額外輸入,從而實(shí)現(xiàn)
    的頭像 發(fā)表于 07-05 09:32 ?920次閱讀

    遞歸神經(jīng)網(wǎng)絡(luò)與循環(huán)神經(jīng)網(wǎng)絡(luò)一樣嗎

    遞歸神經(jīng)網(wǎng)絡(luò)(Recursive Neural Network,RvNN)和循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network,RNN)是兩種不同類(lèi)型的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu),它們?cè)谔幚硇蛄袛?shù)據(jù)
    的頭像 發(fā)表于 07-05 09:28 ?1587次閱讀

    遞歸神經(jīng)網(wǎng)絡(luò)主要應(yīng)用于哪種類(lèi)型數(shù)據(jù)

    處理(NLP) 自然語(yǔ)言處理是遞歸神經(jīng)網(wǎng)絡(luò)最重要的應(yīng)用領(lǐng)域之一。在NLP中,遞歸神經(jīng)網(wǎng)絡(luò)可以用于以下任務(wù): 1.1 語(yǔ)言模型(Language Modeling) 語(yǔ)言模型是預(yù)測(cè)給定詞序列中下一個(gè)詞的概率分布。遞歸神經(jīng)網(wǎng)絡(luò)可以捕
    的頭像 發(fā)表于 07-04 14:58 ?1226次閱讀

    遞歸神經(jīng)網(wǎng)絡(luò)是循環(huán)神經(jīng)網(wǎng)絡(luò)嗎

    遞歸神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network,簡(jiǎn)稱(chēng)RNN)和循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network,簡(jiǎn)稱(chēng)RNN)實(shí)際上是同一個(gè)概念,只是不同的翻譯方式
    的頭像 發(fā)表于 07-04 14:54 ?1506次閱讀

    遞歸神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)、特點(diǎn)、優(yōu)缺點(diǎn)及適用場(chǎng)景

    遞歸神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Networks,簡(jiǎn)稱(chēng)RNN)是一種具有循環(huán)結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò),其核心特點(diǎn)是能夠處理序列數(shù)據(jù),并對(duì)序列中的信息進(jìn)行記憶和傳遞。RNN在自然語(yǔ)言處理、語(yǔ)音
    的頭像 發(fā)表于 07-04 14:52 ?2560次閱讀

    電子發(fā)燒友

    中國(guó)電子工程師最喜歡的網(wǎng)站

    • 2931785位工程師會(huì)員交流學(xué)習(xí)
    • 獲取您個(gè)性化的科技前沿技術(shù)信息
    • 參加活動(dòng)獲取豐厚的禮品