请用非递归方式实现二叉树的先序、中序和后序的遍历打印。
给定一个二叉树的根结点root，请依次返回二叉树的先序，中序和后续遍历(二维数组的形式)。
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class TreeToSequence { public: vector<vector<int> > convert(TreeNode* root) { vector<vector<int> > res; vector<int> tmp; preorder(root,tmp); res.push_back(tmp); tmp.clear(); midorder(root,tmp); res.push_back(tmp); tmp.clear(); posorder(root,tmp); res.push_back(tmp); return res; } // 先序遍历 void preorder(TreeNode* root,vector<int> &tmp){ if(root==NULL) return ; stack<TreeNode*> s; s.push(root); while(!s.empty()){ TreeNode* cur=s.top(); tmp.push_back(cur->val); s.pop(); if(cur->right!=NULL) s.push(cur->right); if(cur->left!=NULL) s.push(cur->left); } } // 中序遍历 void midorder(TreeNode* root,vector<int> &tmp){ if(root==NULL) return ; stack<TreeNode*> s; TreeNode* cur=root; while(!s.empty()||cur!=NULL){ if(cur!=NULL){ s.push(cur); cur=cur->left; }else{ cur=s.top(); tmp.push_back(cur->val); s.pop(); cur=cur->right; } } } // 后序遍历 void posorder(TreeNode* root,vector<int> &tmp){ if(root==NULL) return ; stack<TreeNode*> s1; stack<TreeNode*> s2; s1.push(root); while(!s1.empty()){ TreeNode* cur=s1.top(); s2.push(cur); s1.pop(); if(cur->left!=NULL) s1.push(cur->left); if(cur->right!=NULL) s1.push(cur->right); } while(!s2.empty()){ tmp.push_back(s2.top()->val); s2.pop(); } } };
