C++完成二叉樹非遞歸遍歷辦法實例總結。本站提示廣大學習愛好者:(C++完成二叉樹非遞歸遍歷辦法實例總結)文章只能為提供參考,不一定能成為您想要的結果。以下是C++完成二叉樹非遞歸遍歷辦法實例總結正文
普通來講,二叉樹的遍歷是C++法式員在面試中常常考核的,其實前中後三種次序的遍歷都年夜同小異,本身模仿兩個棧用筆劃畫是不難寫出代碼的。現舉一個非遞歸遍歷的辦法以下,供年夜家參考。
詳細代碼以下:
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++算法進修有所贊助。