您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“C++如何實(shí)現(xiàn)二叉樹的后序遍歷”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“C++如何實(shí)現(xiàn)二叉樹的后序遍歷”吧!
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)值被取出來時(shí),它的左右子結(jié)點(diǎn)要么不存在,要么已經(jīng)被訪問過了。先將根結(jié)點(diǎn)壓入棧,然后定義一個(gè)輔助結(jié)點(diǎn) head,while 循環(huán)的條件是棧不為空,在循環(huán)中,首先將棧頂結(jié)點(diǎn)t取出來,如果棧頂結(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)先被處理。下面來看為什么是這三個(gè)條件呢,首先如果棧頂元素如果沒有左右子結(jié)點(diǎn)的話,說明其是葉結(jié)點(diǎn),而且入棧順序保證了左子結(jié)點(diǎn)先被處理,所以此時(shí)的結(jié)點(diǎn)值就可以直接加入結(jié)果 res 了,然后移出棧,將 head 指向這個(gè)葉結(jié)點(diǎn),這樣的話 head 每次就是指向前一個(gè)處理過并且加入結(jié)果 res 的結(jié)點(diǎn),那么如果棧頂結(jié)點(diǎn)的左子結(jié)點(diǎn)或者右子結(jié)點(diǎn)是 head 的話,說明其子結(jié)點(diǎn)已經(jīng)加入結(jié)果 res 了,那么就可以處理當(dāng)前結(jié)點(diǎn)了。
看到這里,大家可能對 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),則是正常的左-右-根的處理順序。那么回過頭來在看,若 head 初始化為空,且此時(shí)正好左子結(jié)點(diǎn)不存在,那么在壓入根結(jié)點(diǎn)時(shí),head 和左子結(jié)點(diǎn)相等就成立了,此時(shí)就直接打印根結(jié)點(diǎn)了,明顯是錯(cuò)的。所以 head 只要不初始化為空,一切都好說,甚至可以新建一個(gè)結(jié)點(diǎ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ū)別,都是利用了改變先序遍歷的順序來實(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; } };
到此,相信大家對“C++如何實(shí)現(xiàn)二叉樹的后序遍歷”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。