C++实现二叉树非递归遍历方法实例总结
一般来说，二叉树的遍历是C++程序员在面试中经常考察的，其实前中后三种顺序的遍历都大同小异，自己模拟两个栈用笔画画是不难写出代码的。现举一个非递归遍历的方法如下，供大家参考。
具体代码如下：
classSolution{
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);
}
returnout;
}
vector<int>inorderTraversal(TreeNode*root){
stack<TreeNode*>s;
vector<int>out;
TreeNode*node=root;
booldone=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;
}
}
}
returnout;
}
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());
returnout;
}
};
希望本文所述对大家的C++算法学习有所帮助。