二叉树的遍历 非递归实现 栈 c++

一、对于一棵二叉树的而言，最普遍的操作就是进行遍历，遍历又分先序遍历，中序遍历，后序遍历，层序遍历。本次博客主要是针对前面三种遍历方式，一般的方法就是采用递归，即逐个根节点进行递归操作，那么如何采用非递归进行遍历呢，这里就需要借助于栈这种数据结构。

二、下面以具体的题目及代码进行讲解（题目是leetcode在线编程）

1.求给定的二叉树的前序遍历

这里以具体的例子进行讲解

定义一个栈和输出序列容器，循环结束条件是栈为空且根结点为空，这表示已经遍历结束了。开始根结点5不为空进入循环，输出5的value值，5进栈，此时root变为5的左子树4，同理1进栈

此时s包含 1 4 5（1为栈顶）

1的左子树为空，则进入判断，如果栈非空，则弹出1开始遍历右子树，此时右子树为空，则返回到4，遍历4的右子树。重复操作最后输出先序遍历。

vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        /*
        //递归
        if(root==NULL)
            return res;
        else{
            res.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return res;*/
        //非递归 栈
        stack<TreeNode*>s;
        vector<int>reg;
        if(root==NULL)
            return reg;
        while(!s.empty()||root!=NULL){
            while(root!=NULL){
                reg.push_back(root->val);
                s.push(root);
                root=root->left;
            }
            if(!s.empty()){
                TreeNode* temp=s.top();
                s.pop();
                root=temp->right;
            }
        }
        return reg;
    }
           

2.给出一棵二叉树，返回这棵树的中序遍历

中序遍历与先序遍历基本相同，只是输出value值的语句位置不同而已。

vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        /*
        //复习递归
        if(root==NULL)
            return vec;
        else{
            inorderTraversal(root->left);
            vec.push_back(root->val);
            inorderTraversal(root->right);
        }
        return vec;*/
        
        //非递归
        vector<int>vec;
        if(root==NULL)
            return vec;
        stack<TreeNode*>s;
        while(!s.empty()||root!=NULL){
            while(root!=NULL){
                s.push(root);
                root=root->left;
            }
            if(!s.empty()){
                TreeNode* temp=s.top();
                s.pop();
                vec.push_back(temp->val);
                root=temp->right;
            }
        }
        return vec;
    }
           

3.求给定的二叉树的后序遍历

vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        /*if(root!=NULL){
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            vec.push_back(root->val);
        }
        return vec;*/
        vector<int>vec;
        if(root==NULL)
            return vec;
        stack<TreeNode*>s;
        while(root!=NULL||!s.empty()){
            while(root!=NULL){
                s.push(root->left);
                vec.push_back(root->val);
                root=root->right;
            }
            root=s.top();
            s.pop();
        }
        reverse(vec.begin(),vec.end());
        return vec;
        
    }