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++算法学习有所帮助。
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短