算法随想Day12【二叉树】| LC144、LC145、LC94-二叉树的前中后序遍历

标签：遍历 curr TreeNode stk vct 二叉树 Day12 LC94 root

LC144、LC145、LC94-二叉树的前中后遍历

二叉树递归遍历

比较容易实现

二叉树非递归遍历

迭代法需要通过使用“栈”来模拟递归的过程

前序遍历：

放入root节点，弹出每个节点时，依次push入该节点的右孩子和左孩子

后序遍历：

由中左右->中右左，翻转结果中右左->左右中，即为后续遍历

中序遍历：

vector记录访问过的节点。先一路向左走，有左孩子的话，就一直push入，直到没左孩子了，pop出，并回到中节点

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x = 0) : val(x), left(nullptr), right(nullptr) {  }
};

class Tree
{
    private:
        TreeNode* _root;

    public:

        /*********递归遍历**********/
        void pre_traversal(TreeNode* curr, vector<int>& vct)
        {
            if(curr == nullptr)
            {
                return;
            }
            // 前序遍历--中左右
            vct.emplace_back(curr->val);
            pre_traversal(curr->left, vct);
            pre_traversal(curr->right, vct);   
        }

        void in_traversal(TreeNode* curr, vector<int>& vct)
        {
            if(curr == nullptr)
            {
                return;
            }
            // 中序遍历--左中右
            in_traversal(curr->left, vct);
            vct.emplace_back(curr->val);
            in_traversal(curr->right, vct);   
        }

        void post_traversal(TreeNode* curr, vector<int>& vct)
        {
            if(curr == nullptr)
            {
                return;
            }
            // 后序遍历--左右中
            post_traversal(curr->left, vct);
            vct.emplace_back(curr->val);
            post_traversal(curr->right, vct);   
        }

        vector<int> preorderTraversal(TreeNode* root)
        {
            vector<int> vct;
            pre_traversal(root, vct);
            return vct;
        }

        vector<int> inorderTraversal(TreeNode* root)
        {
            vector<int> vct;
            in_traversal(root, vct);
            return vct;
        }

        vector<int> postorderTraversal(TreeNode* root)
        {
            vector<int> vct;
            post_traversal(root, vct);
            return vct;
        }


        /*********迭代遍历**********/

        // 前序遍历--中左右(自写成功运行lc144)
        vector<int> preorderTraversal_iteration(TreeNode* root)
        {
            vector<int> vct;
            stack<TreeNode*> stk;
            
            if(root == nullptr) 
                return vct;

            stk.push(root);

            while(!stk.empty())
            {   
                TreeNode* curr = stk.top();
                vct.emplace_back(curr->val);
                stk.pop();

                if(curr->right) stk.push(curr->right);
                if(curr->left) stk.push(curr->left);
            }

            return vct;
        }

        // 后序遍历--左右中，即前序中的中左右，现改为中右左，在将vct整体镜像翻转所得
        vector<int> postorderTraversal_iteration(TreeNode* root)
        {
            vector<int> vct;
            stack<TreeNode*> stk;
            
            if(root == nullptr)
            {
                return vct;
            }

            stk.push(root);

            while(!stk.empty())
            {   
                TreeNode* curr = stk.top();
                vct.emplace_back(curr->val);
                stk.pop();
                
                if(curr->left) stk.push(curr->left);
                if(curr->right) stk.push(curr->right);
            }

            reverse(vct.begin(), vct.end());
            return vct;
        }

        // 中序遍历--左中右
        vector<int> inorderTraversal_iteration(TreeNode* root)
        {
            vector<int> vct;
            stack<TreeNode*> stk;       // 栈中元素代表遍历过的，栈顶表示当前访问的节点
            
            if(root == nullptr) 
                return vct;

            TreeNode* curr = root;      // curr可认为是当前的根节点

            while(curr != nullptr || !stk.empty())
            {   
                if(curr != nullptr)     // 有左子节点，压入，并将左子节点当作新的当前根节点
                {
                    stk.push(curr);
                    curr = curr->left;
                }
                else                    // 发现没左子节点了，退一步改将当前根节点改回上一步，并pop出，并将其右子节点当作新的当前根节点
                {
                    curr = stk.top();
                    stk.pop();
                    vct.emplace_back(curr->val);
                    curr = curr->right;
                }
            }

            return vct;
        }
};

标签：遍历,curr,TreeNode,stk,vct,二叉树,Day12,LC94,root
From： https://www.cnblogs.com/Mingzijiang/p/17121208.html