当前位置: 编程技术>c/c++/嵌入式
C++实现二叉树非递归遍历方法实例总结
来源: 互联网 发布时间:2014-10-28
本文导语: 一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的。现举一个非递归遍历的方法如下,供大家参考。 具体代码如下: class Solution { ...
一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的。现举一个非递归遍历的方法如下,供大家参考。
具体代码如下:
class Solution { public: vector preorderTraversal(TreeNode *root) { vector out; stack 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 inorderTraversal(TreeNode *root) { stack s; vector 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 postorderTraversal(TreeNode *root) { vector out; stack 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++算法学习有所帮助。