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++算法学习有所帮助。
赞 (0)