二叉树前序、中序、后序遍历的迭代实现

c/c++

浏览数:180

2019-3-30

AD:资源代下载服务

二叉树的前序、中序、后序遍历用递归实现较为简单。然而,利用递归实现则有一些挑战。现将几种常见的实现方式做简单介绍:

二叉树节点定义如下:

struct ListNode {
     int val;
      ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};

一、前序遍历

前序遍历的顺序为:中,左,右。至少有两种方案:

//方案一:先后将右子树和左子放入栈中,利用栈后入先出的原理遍历。
 vector<int> preorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->right) st.push(p->right);
         if(p->left) st.push(p->left);
     }
     return res;
 }
//方案二:循环左子数,将右子树放入栈中。左子树为空时,依次弹栈,从最下层开始访问右子树。
 vector<int> preorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     st.push(root);
     while(!st.empty()){
         TreeNode* p = st.top();
         res.push_back(p->val);
         st.pop();
         while(p->left){
             res.push_back(p->left->val);
             if(p->right) st.push(p->right);
             p = p->left;
         }
         if(p->right) st.push(p->right);
     }
     return res;
 }

二、中序遍历

中序遍历的顺序为:左,中,右。其经典思路为:当前节点有左子节点时,将当前节点压栈,并将左子节点作为当前处理;当前节点无左子节点时,表示左子树都已遍历完成,此时访问当前节点,并将右子节点设为当前节点。

 vector<int> inorderTraversal(TreeNode *root) {
     vector<int> res;
     if(!root)
         return res;
     stack<TreeNode*> st;
     TreeNode* p = root;
     while(p || !st.empty()){
         if(p){
             st.push(p);
             p = p->left;
         }
         else{
             p = st.top();
             res.push_back(p->val);
             st.pop();
             p = p->right;
         }
     }
     return res;
 }

三、后续遍历

后序遍历的顺序为:左,右,中。以下给出两种方案:

//方案一:当前节点被读取的条件为:无左右孩子,或者上一次读取的为其左右孩子。
//否则按照先右后左的方式对子节点压栈。

 vector<int> postorderTraversal(TreeNode *root){
     vector<int> res;
     if(!root)  
         return res;
     stack<TreeNode *> st;
     TreeNode * pre = nullptr;
     st.push(root);
     while(!st.empty()){
         TreeNode * p = st.top();
         if( (!p->left && !p->right) ||
             (pre && (pre == p->left || pre == p->right)) ){
             res.push_back(p->val);
             st.pop();
             pre = p;
         }
         else{
             if(p->right) st.push(p->right);
             if(p->left) st.push(p->left);
         }
     }
     return res;        
 }
//方案二:后序遍历有一种巧妙的方式:前序遍历根节点,先后将左右子节点压栈。
//这样的遍历顺序为:中,右,左。最后reverse结果,则遍历结果变为:左,右,中。

 vector<int> postorderTraversal(TreeNode *root){
     vector<int> res;
     if(!root)  
         return res;
     stack<TreeNode *> st;
     st.push(root);
     while(!st.empty()){
         TreeNode * p = st.top();
         res.push_back(p->val);
         st.pop();
         if(p->left) st.push(p->left);
         if(p->right) st.push(p->right);
     }
     reverse(res.begin(), res.end());
     return res;        
 }