一、先序遍歷

先序遍歷：先遍歷一顆樹的根節(jié)點(diǎn)，后遍歷左子樹，最后遍歷右子樹

?

?
先序遍歷序列： 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

題目鏈接

1.遞歸

分解子問題方法

class Solution {
public:
    void preOrder(TreeNode* root,vector<int>& str)
    {
        if(root==NULL)return;
        str.push_back(root->val);
        preOrder(root->left,str);
        preOrder(root->right,str);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> str;
        preOrder(root,str);
        return str;
    }
};

2.非遞歸

思路：將一顆二叉樹看做兩個(gè)部分，一個(gè)部分是左路節(jié)點(diǎn)，另一個(gè)部分是左路節(jié)點(diǎn)的右子樹，先將二叉樹的左路節(jié)點(diǎn)全部入棧，再依次出棧，出棧的過程中將這個(gè)節(jié)點(diǎn)的右子樹按相同方法將左路節(jié)點(diǎn)全部入棧，然后依次出棧，出棧的方法與上面相同，模擬遞歸調(diào)用的方法實(shí)現(xiàn)非遞歸，此時(shí)的入棧順序就是先序遍歷序列

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur=root;
        vector<int> v;
        while(cur||!st.empty())
        {
            //訪問一棵樹的開始
            //  1、訪問左路節(jié)點(diǎn)，左路節(jié)點(diǎn)入棧，后續(xù)一次訪問左路節(jié)點(diǎn)的右子樹
            while(cur)
            {
                v.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }

            //一次訪問左路節(jié)點(diǎn)的右子樹
            TreeNode* top=st.top();
            st.pop();

            //子問題的方式訪問右子樹
            cur=top->right;
        }
        return v;
    }
};

二、中序遍歷

題目鏈接

中序遍歷：先遍歷一顆樹的左子樹，然后遍歷根節(jié)點(diǎn)，最后遍歷右子樹
?
?
中序遍歷序列：4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

1.遞歸

遞歸調(diào)用分解子問題，與前序遍歷遞歸思路相同

class Solution {
public:
    void inorder(TreeNode* root,vector<int>& res)
    {
        if(root==NULL)return;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);

    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        return res;
    }
};

2.非遞歸

與前序遍歷相似，前序遍歷是在入棧的順序?yàn)榍靶虮闅v序列，而中序遍歷則是出棧的順序則為中序遍歷序列

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur=root;
        vector<int> v;
        while(cur||!st.empty())
        {
            //訪問一棵樹的開始
            //  1、訪問左路節(jié)點(diǎn)，左路節(jié)點(diǎn)入棧，后續(xù)一次訪問左路節(jié)點(diǎn)的右子樹
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            //一次訪問左路節(jié)點(diǎn)的右子樹
            TreeNode* top=st.top();
            st.pop();
            v.push_back(top->val);
            //子問題的方式訪問右子樹
            cur=top->right;
        }
        return v;

    }
};

三、后序遍歷

后序遍歷：先遍歷一顆樹的左子樹，然后遍歷右子樹，最后遍歷根節(jié)點(diǎn)
?
?
后續(xù)遍歷序列：4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

題目鏈接

1.遞歸

分解子問題

class Solution {
public:
    void postOrder(TreeNode* root,vector<int>& ret)
    {
        if(root==NULL)return;
        postOrder(root->left,ret);
        postOrder(root->right,ret);
        ret.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        postOrder(root,ret);
        return ret;
    }
};

2.非遞歸

后續(xù)遍歷的非遞歸要比前序和中序遍歷的非遞歸復(fù)雜一點(diǎn)，我們要在前面前序遍歷和中序遍歷非遞歸的算法上進(jìn)行一些改進(jìn)，創(chuàng)建一個(gè)變量prev，用來記錄訪問當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，如果當(dāng)前左路節(jié)點(diǎn)的右子樹為空或者已經(jīng)訪問過右子樹就需將當(dāng)前接節(jié)點(diǎn)出棧，此時(shí)的出棧順序即為后續(xù)遍歷序列。

文章來源地址http://www.zghlxwxcb.cn/news/detail-624887.html

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur=root;
        TreeNode* prev=NULL;
        vector<int> v;
        while(cur||!st.empty())
        {
            //訪問一棵樹的開始
            //  1、訪問左路節(jié)點(diǎn)，左路節(jié)點(diǎn)入棧，后續(xù)一次訪問左路節(jié)點(diǎn)的右子樹
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            TreeNode* top=st.top();
            //一個(gè)節(jié)點(diǎn)右子樹為空或者上一個(gè)訪問節(jié)點(diǎn)是右子樹的根，說明右子樹訪問過濾，可以訪問根節(jié)點(diǎn)了
            if(top->right==nullptr||top->right==prev)
            {
                prev=top;
                v.push_back(top->val);
                st.pop();
            }else cur=top->right;
        }
        return v;
    }
};

到了這里，關(guān)于二叉樹的遍歷（先序遍歷，中序遍歷，后序遍歷）遞歸與非遞歸算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！