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;// 轉(zhuǎn)化成子問題訪問右子樹
        }
        return v;
    }
};

二、二叉樹的中序遍歷

題目鏈接

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

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 方法二

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

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

1?? 從左子樹回來，現(xiàn)在要先訪問右子樹

2?? 從右子樹回來，左右子樹已經(jīng)訪問完畢，再訪問根。

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

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++實現(xiàn)二叉樹非遞歸遍歷算法詳解的文章就介紹到這了,更多相關C++二叉樹非遞歸遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: