C++實現(xiàn)二叉樹非遞歸遍歷方法實例總結
更新時間：2014年08月27日 11:27:05 投稿：shichen2014
這篇文章主要介紹了C++實現(xiàn)二叉樹非遞歸遍歷方法實例總結,是算法設計中比較經典的一個遍歷算法,需要的朋友可以參考下
一般來說，二叉樹的遍歷是C++程序員在面試中經常考察的，其實前中后三種順序的遍歷都大同小異，自己模擬兩個棧用筆畫畫是不難寫出代碼的?，F(xiàn)舉一個非遞歸遍歷的方法如下，供大家參考。
具體代碼如下：
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> out;
stack<TreeNode*> s;
s.push(root);
while(!s.empty() && root){
TreeNode *node = s.top();
out.push_back(node->val);
s.pop();
if(node->right) s.push(node->right);
if(node->left) s.push(node->left);
}
return out;
}
vector<int> inorderTraversal(TreeNode *root) {
stack<TreeNode *> s;
vector<int> out;
TreeNode *node = root;
bool done = false;
while(!done){
if(node){
s.push(node);
node = node->left;
}else {
if(s.empty()) done = true;
else{
node = s.top();
s.pop();
out.push_back(node->val);
node = node->right;
}
}
}
return out;
}
vector<int> postorderTraversal(TreeNode *root) {
vector<int> out;
stack<TreeNode*> s;
TreeNode* node = root;
s.push(node);
while(!s.empty()&&node){
node = s.top();
out.push_back(node->val);
s.pop();
if(node->left) s.push(node->left);
if(node->right)s.push(node->right);
}
reverse(out.begin(),out.end());
return out;
}
};
希望本文所述對大家的C++算法學習有所幫助。
相關文章
這篇文章主要為大家詳細介紹了C語言鏈表實現(xiàn)貪吃蛇游戲源碼，適合C語言入門者學習閱讀，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
題目：輸入一個字符串，輸出該字符串中對稱的子字符串的最大長度。比如輸入字符串“google”，由于該字符串里最長的對稱子字符串是“goog”，因此輸出4。2013-03-03
C語言循環(huán)隊列與用隊列實現(xiàn)棧問題解析
循環(huán)隊列又叫環(huán)形隊列，是一種特殊的隊列。循環(huán)隊列解決了隊列出隊時需要將所有數(shù)據前移一位的問題，本篇帶你一起看看循環(huán)隊列的問題和怎樣用隊列實現(xiàn)棧2022-04-04
這篇文章主要介紹了C++ vector類的模擬實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
這篇文章主要介紹了C++實現(xiàn)LeetCode( 69.求平方根),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了OpenCV利用背景建模檢測運動物體，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++中引用傳遞與指針傳遞的區(qū)別(面試常見),需要的朋友可以參考下2018-03-03
Sublime Text 3 實現(xiàn)C++代碼的編譯和運行示例
下面小編就為大家?guī)硪黄猄ublime Text 3 實現(xiàn)C++代碼的編譯和運行示例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-09-09
這篇文章主要為大家詳細介紹了C++實現(xiàn)寵物商店信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
大家好，本篇文章主要講的是C語言實現(xiàn)煙花表白程序代碼，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02