快捷導(dǎo)航

C++二叉樹的前序中序后序非遞歸實現(xiàn)方法詳細講解

更新時間：2023年03月08日 11:23:25 作者：平凡的人1

前序遍歷的順序是根、左、右。任何一顆樹都可以認(rèn)為分為左路節(jié)點，左路節(jié)點的右子樹。先訪問左路節(jié)點，再來訪問左路節(jié)點的右子樹。把訪問左路節(jié)點的右子樹看成一個子問題，就可以完整遞歸訪問了

二叉樹的前序遍歷

前序遍歷的順序是根、左、右。任何一顆樹都可以認(rèn)為分為左路節(jié)點，左路節(jié)點的右子樹。先訪問左路節(jié)點，再來訪問左路節(jié)點的右子樹。把訪問左路節(jié)點的右子樹看成一個子問題，就可以完整遞歸訪問了。

先定義棧st存放節(jié)點、v存放值，TreeNode* cur，cur初始化為root。

當(dāng)cur不為空或者棧不為空的時候(一開始棧是空的，cur不為空)，循環(huán)繼續(xù)：先把左路節(jié)點存放進棧中，同時把值存入v中，一直循環(huán)，直到此時的左路節(jié)點為空，訪問結(jié)束。在彈出棧頂元素top，把top->right賦值給我們的cur，就可以轉(zhuǎn)化成子問題去訪問左路節(jié)點的右子樹了。

棧st不為空說明此時還有左路節(jié)點的右子樹還沒訪問，cur不為空說明此時還有樹要去訪問。當(dāng)兩個同時為空時，循環(huán)結(jié)束，最終得到前序遍歷。
一個節(jié)點出棧說明這個節(jié)點及其左子樹已經(jīng)訪問完了，因為我們是先把左路節(jié)點存入棧中，此時還剩右子樹沒有訪問。

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

二叉樹的中序遍歷

中序遍歷是左、根、右。左子樹訪問完之后才能去訪問根。左路節(jié)點一直走直到左子樹訪問完，入棧的過程中不去進行訪問（存放數(shù)值到v中），當(dāng)左路節(jié)點出棧之后，也就是從棧中彈出進行訪問。

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

二叉樹的后序遍歷

后序的遍歷順序是左、右、根。與前面的相比，比較麻煩，我們需要把左子樹和右子樹訪問完再去訪問根。我們定義一個棧，在棧里面取到一個節(jié)點時：右子樹是否訪問過，如果沒有訪問，迭代子問題訪問，如果訪問過了，則訪問這個根節(jié)點，pop出棧

如果top的右子樹為空或者右子樹已經(jīng)訪問過了（上一個訪問節(jié)點是右子樹的根），那么說明右子樹不用訪問或者訪問過了，可以訪問根top;當(dāng)右子樹不為空，且沒有訪問過，則迭代子問題訪問。

通過prev來判斷上一次訪問的節(jié)點：如果prev等于top->right時，表示棧頂節(jié)點的右子樹已經(jīng)訪問過了，可以彈出棧頂節(jié)點并訪問它。

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode*> st;
        TreeNode*cur = root;
        TreeNode*prev = nullptr;
        while(cur||!st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode*top = st.top();
            //top的右子樹為空，或者右子樹已經(jīng)訪問過了（上一個訪問節(jié)點時右子樹的根）那么說明右子樹不用訪問或者訪問過了，可以訪問根top
            //右子樹不為空，且沒有訪問， 則迭代子問題訪問
            if(top->right==nullptr||top->right==prev)
            {
                st.pop();
                v.push_back(top->val);
                prev = top;
            }
            else
            {
                cur = top->right;
            }
        }
        return v;
    }
};