C++怎么實現二叉樹非遞歸遍歷算法

本文小編為大家詳細介紹“C++怎么實現二叉樹非遞歸遍歷算法”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C++怎么實現二叉樹非遞歸遍歷算法”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

一、二叉樹的前序遍歷

題目鏈接

我們可以把任何一棵樹看成左路節點，左路節點和右子樹。先訪問左路節點，再訪問左路節點的右子樹。在右子樹中也重復這種循環，就是非遞歸遍歷二叉樹的思想。

解釋：

棧st存放節點，v存放數值，cur初始化為root。

循環條件是棧不為空或者cur不為空(訪問最后一個節點之前棧就已經為空了)，循環遍歷左子樹并且把左子樹入棧，同時把值存入v中。然后彈出棧頂元素，并且把棧頂元素的右子樹賦值給cur，這樣就形成了遍歷。

當棧不為空的時候說明還有左路節點的右子樹沒有被訪問，當cur不為空的時候說明還有樹要被訪問。當同時為空的時候才是訪問完成。當一個節點出棧的時候說明此時該節點及該節點的左子樹已經被訪問完成了。

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }
            TreeNode* node = st.top();
            st.pop();
            cur = node->right;// 轉化成子問題訪問右子樹
        }
        return v;
    }
};

二、二叉樹的中序遍歷

題目鏈接

因為中序遍歷的訪問順序是左根右，跟前序遍歷不同，所以我們讓左節點入棧的時候先不訪問，出棧（說明左子樹訪問完了）時在訪問節點。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(!st.empty() || cur)
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* node = st.top();
            st.pop();
            v.push_back(node->val);
            cur = node->right;
        }
        return v;
    }
};

三、二叉樹的后序遍歷

3.1 方法一

首先我們知道后序遍歷就是左右根，而我們可以把訪問順序變成根右左，然后再逆置順序。而根右左就跟前序遍歷的方法一樣：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->right;
            }
            TreeNode* node = st.top();
            st.pop();
            cur = node->left;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

3.2 方法二

按照常規的遍歷方法走左右根，但是這里有一個問題：

當訪問到根的時候有兩種情況：

1?? 從左子樹回來，現在要先訪問右子樹

2?? 從右子樹回來，左右子樹已經訪問完畢，再訪問根。

針對這種情況我們可以在加一個變量來確定是第幾次訪問根，如果是第一次就訪問右子樹，如果是第二次就訪問。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<pair<TreeNode*, bool>> st;
        vector<int> v;
        TreeNode* cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(make_pair(cur, false));
                cur = cur->left;
            }
            TreeNode* node = st.top().first;
            if(st.top().second == true)
            {
                st.pop();
                v.push_back(node->val);
            }
            else
            {
                st.top().second = true;
                cur = node->right;
            }
        }
        return v;
    }
};

讀到這里，這篇“C++怎么實現二叉樹非遞歸遍歷算法”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。