欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)LeetCode(145.二叉樹的后序遍歷)

 更新時(shí)間:2021年07月19日 16:50:45   作者:Grandyang  
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(145.二叉樹的后序遍歷),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 145. Binary Tree Postorder Traversal 二叉樹的后序遍歷

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
\
2
/
3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

經(jīng)典題目,求二叉樹的后序遍歷的非遞歸方法,跟前序,中序,層序一樣都需要用到棧,后序的順序是左-右-根,所以當(dāng)一個(gè)結(jié)點(diǎn)值被取出來(lái)時(shí),它的左右子結(jié)點(diǎn)要么不存在,要么已經(jīng)被訪問(wèn)過(guò)了。先將根結(jié)點(diǎn)壓入棧,然后定義一個(gè)輔助結(jié)點(diǎn) head,while 循環(huán)的條件是棧不為空,在循環(huán)中,首先將棧頂結(jié)點(diǎn)t取出來(lái),如果棧頂結(jié)點(diǎn)沒有左右子結(jié)點(diǎn),或者其左子結(jié)點(diǎn)是 head,或者其右子結(jié)點(diǎn)是 head 的情況下。將棧頂結(jié)點(diǎn)值加入結(jié)果 res 中,并將棧頂元素移出棧,然后將 head 指向棧頂元素;否則的話就看如果右子結(jié)點(diǎn)不為空,將其加入棧,再看左子結(jié)點(diǎn)不為空的話,就加入棧,注意這里先右后左的順序是因?yàn)闂5暮笕胂瘸龅奶攸c(diǎn),可以使得左子結(jié)點(diǎn)先被處理。下面來(lái)看為什么是這三個(gè)條件呢,首先如果棧頂元素如果沒有左右子結(jié)點(diǎn)的話,說(shuō)明其是葉結(jié)點(diǎn),而且入棧順序保證了左子結(jié)點(diǎn)先被處理,所以此時(shí)的結(jié)點(diǎn)值就可以直接加入結(jié)果 res 了,然后移出棧,將 head 指向這個(gè)葉結(jié)點(diǎn),這樣的話 head 每次就是指向前一個(gè)處理過(guò)并且加入結(jié)果 res 的結(jié)點(diǎn),那么如果棧頂結(jié)點(diǎn)的左子結(jié)點(diǎn)或者右子結(jié)點(diǎn)是 head 的話,說(shuō)明其子結(jié)點(diǎn)已經(jīng)加入結(jié)果 res 了,那么就可以處理當(dāng)前結(jié)點(diǎn)了。

看到這里,大家可能對(duì) head 的作用,以及為何要初始化為 root,還不是很清楚,這里再解釋一下。head 是指向上一個(gè)被遍歷完成的結(jié)點(diǎn),由于后序遍歷的順序是左-右-根,所以一定會(huì)一直將結(jié)點(diǎn)壓入棧,一直到把最左子結(jié)點(diǎn)(或是最左子結(jié)點(diǎn)的最右子結(jié)點(diǎn))壓入棧后,開始進(jìn)行處理。一旦開始處理了,head 就會(huì)被重新賦值。所以 head 初始化值并沒有太大的影響,唯一要注意的是不能初始化為空,因?yàn)樵谂袛嗍欠翊蛴〕霎?dāng)前結(jié)點(diǎn)時(shí)除了判斷是否是葉結(jié)點(diǎn),還要看 head 是否指向其左右子結(jié)點(diǎn),如果 head 指向左子結(jié)點(diǎn),那么右子結(jié)點(diǎn)一定為空,因?yàn)槿霔m樞蚴歉?右-左,不存在右子結(jié)點(diǎn)還沒處理,就直接去處理根結(jié)點(diǎn)了的情況。若 head 指向右子結(jié)點(diǎn),則是正常的左-右-根的處理順序。那么回過(guò)頭來(lái)在看,若 head 初始化為空,且此時(shí)正好左子結(jié)點(diǎn)不存在,那么在壓入根結(jié)點(diǎn)時(shí),head 和左子結(jié)點(diǎn)相等就成立了,此時(shí)就直接打印根結(jié)點(diǎn)了,明顯是錯(cuò)的。所以 head 只要不初始化為空,一切都好說(shuō),甚至可以新建一個(gè)結(jié)點(diǎn)也沒問(wèn)題。將 head 初始化為 root,也可以,就算只有一個(gè) root 結(jié)點(diǎn),那么在判定葉結(jié)點(diǎn)時(shí)就將 root 打印了,然后就跳出 while 循環(huán)了,也不會(huì)出錯(cuò)。代碼如下:

解法一:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        TreeNode *head = root;
        while (!s.empty()) {
            TreeNode *t = s.top();
            if ((!t->left && !t->right) || t->left == head || t->right == head) {
                res.push_back(t->val);
                s.pop();
                head = t;
            } else {
                if (t->right) s.push(t->right);
                if (t->left) s.push(t->left);
            }
        }
        return res;
    }
};

由于后序遍歷的順序是左-右-根,而先序遍歷的順序是根-左-右,二者其實(shí)還是很相近的,可以先在先序遍歷的方法上做些小改動(dòng),使其遍歷順序變?yōu)楦?右-左,然后翻轉(zhuǎn)一下,就是左-右-根啦,翻轉(zhuǎn)的方法我們使用反向Q,哦不,是反向加入結(jié)果 res,每次都在結(jié)果 res 的開頭加入結(jié)點(diǎn)值,而改變先序遍歷的順序就只要該遍歷一下入棧順序,先左后右,這樣出棧處理的時(shí)候就是先右后左啦,參見代碼如下:

解法二:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            res.insert(res.begin(), t->val);
            if (t->left) s.push(t->left);
            if (t->right) s.push(t->right);
        }
        return res;
    }
};

那么在 Binary Tree Preorder Traversal 中的解法二也可以改動(dòng)一下變成后序遍歷,改動(dòng)的思路跟上面的解法一樣,都是先將先序遍歷的根-左-右順序變?yōu)楦?右-左,再翻轉(zhuǎn)變?yōu)楹笮虮闅v的左-右-根,翻轉(zhuǎn)還是改變結(jié)果 res 的加入順序,然后把更新輔助結(jié)點(diǎn)p的左右順序換一下即可,代碼如下:

解法三:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while (!s.empty() || p) {
            if (p) {
                s.push(p);
                res.insert(res.begin(), p->val);
                p = p->right;
            } else {
                TreeNode *t = s.top(); s.pop();
                p = t->left;
            }
        }
        return res;
    }
};

論壇上還有一種雙棧的解法,其實(shí)本質(zhì)上跟解法二沒什么區(qū)別,都是利用了改變先序遍歷的順序來(lái)實(shí)現(xiàn)后序遍歷的,參見代碼如下:

解法四:

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s1, s2;
        s1.push(root);
        while (!s1.empty()) {
            TreeNode *t = s1.top(); s1.pop();
            s2.push(t);
            if (t->left) s1.push(t->left);
            if (t->right) s1.push(t->right);
        }
        while (!s2.empty()) {
            res.push_back(s2.top()->val); s2.pop();
        }
        return res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(145.二叉樹的后序遍歷)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)二叉樹的后序遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • 使用C++實(shí)現(xiàn)Range序列生成器的示例代碼

    使用C++實(shí)現(xiàn)Range序列生成器的示例代碼

    在C++編程中,經(jīng)常需要迭代一系列數(shù)字或其他可迭代對(duì)象,本文將使用C++來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的Range封裝,文中的示例代碼講解詳細(xì),感興趣的可以了解下
    2023-11-11
  • C++流程控制中用于跳轉(zhuǎn)的return和goto語(yǔ)句學(xué)習(xí)教程

    C++流程控制中用于跳轉(zhuǎn)的return和goto語(yǔ)句學(xué)習(xí)教程

    這篇文章主要介紹了C++流程控制中用于跳轉(zhuǎn)的return和goto語(yǔ)句學(xué)習(xí)教程,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2016-01-01
  • C/C++中棧(stack)&堆(heap)詳解及其作用介紹

    C/C++中棧(stack)&堆(heap)詳解及其作用介紹

    這篇文章主要介紹了C/C++中棧(stack)&堆(heap)詳解及其作用,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-09-09
  • C語(yǔ)言手把手帶你掌握帶頭雙向循環(huán)鏈表

    C語(yǔ)言手把手帶你掌握帶頭雙向循環(huán)鏈表

    帶頭雙向循環(huán)鏈表:結(jié)構(gòu)最復(fù)雜,一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu),都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜,但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì),實(shí)現(xiàn)反而簡(jiǎn)單
    2022-04-04
  • C++代碼實(shí)現(xiàn)逆波蘭式

    C++代碼實(shí)現(xiàn)逆波蘭式

    這篇文章主要為大家詳細(xì)介紹了C++代碼實(shí)現(xiàn)逆波蘭式,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-11-11
  • C++使用string的大數(shù)乘法運(yùn)算(3)

    C++使用string的大數(shù)乘法運(yùn)算(3)

    這篇文章主要為大家詳細(xì)介紹了C++使用string的大數(shù)乘法運(yùn)算,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-09-09
  • C++中利用cout和fstream采用非科學(xué)計(jì)數(shù)法輸出

    C++中利用cout和fstream采用非科學(xué)計(jì)數(shù)法輸出

    這篇文章主要介紹了C++中利用cout和fstream采用非科學(xué)計(jì)數(shù)法輸出方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-11-11
  • c語(yǔ)言中聯(lián)合體和枚舉用法詳解

    c語(yǔ)言中聯(lián)合體和枚舉用法詳解

    結(jié)構(gòu)體、聯(lián)合體是C語(yǔ)言中的構(gòu)造類型,結(jié)構(gòu)體我們平時(shí)應(yīng)該都用得很多,下面這篇文章主要給大家介紹了關(guān)于c語(yǔ)言中聯(lián)合體和枚舉用法的相關(guān)資料,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-12-12
  • c++ 盡量不要使用#define 而是用const、enum、inline替換。

    c++ 盡量不要使用#define 而是用const、enum、inline替換。

    為什么這么說(shuō)呢?或許很多程序員已經(jīng)習(xí)慣在文件開始使用大量的#define語(yǔ)句
    2013-01-01
  • Vs?Code中C/C++配置launch.json和tasks.json文件詳細(xì)步驟

    Vs?Code中C/C++配置launch.json和tasks.json文件詳細(xì)步驟

    使用VSCode開發(fā)C/C++程序,需要配置tasks.json/launch.json,下面這篇文章主要給大家介紹了關(guān)于Vs?Code中C/C++配置launch.json和tasks.json文件的相關(guān)資料,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下
    2024-01-01

最新評(píng)論