BinaryTree，Preordertraversal，Inordertraversal，and Postordertraversal的三種非遞歸實作方式

二叉樹周遊的三種非遞歸實作方式

       二叉樹的前序周遊，中序周遊，後續周遊是三種十分基礎的便利方式，大多數人對其三種遞歸方式的周遊比較熟悉。這篇文章主要針對LeetCode上面的題目，分别對該三種周遊的非遞歸周遊方式進行了仿真，主要用到的資料結構是棧。

       初學者對三種序列的順序容易搞混淆，這裡首先提供一種簡單的記憶方式。一顆二叉樹簡單分為根節點，左節點，右節點。按照根節點在周遊中的順序，例如，前序，那麼就是根節點在前面，可以很好的記憶三種周遊方式。

後續周遊

非遞歸實作

Leecode145題：點選打開連結

vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        stack<TreeNode*>toVisit;
        TreeNode* pCurrent=root;
        TreeNode* pLastNode=nullptr;
        while(pCurrent||!toVisit.empty()){
            if(pCurrent){
                toVisit.push(pCurrent);
                pCurrent=pCurrent->left;
            }
            else{
                TreeNode* pTop=toVisit.top();
                if(pTop->right&&pLastNode!=pTop->right){
                    pCurrent=pTop->right;
                }
                else{
                    res.push_back(pTop->val);
                    pLastNode=pTop;
                    toVisit.pop();
                }
            }
        }
        return res;
    }
           

中序周遊

非遞歸實作

Leecode94題：點選打開連結

vector<int> inorderTraversal(TreeNode* root) 
        vector<int> res;
        stack<TreeNode*> toVisit;
        TreeNode* pCurrent = root;
        while (pCurrent || !toVisit.empty()) {
            if (pCurrent) {
                toVisit.push(pCurrent);
                pCurrent = pCurrent -> left;
            }
            else {
                pCurrent = toVisit.top();
                toVisit.pop();
                res.push_back(pCurrent -> val);
                pCurrent = pCurrent -> right;
            }
        }
        return res;
    }
           

前序周遊

非遞歸實作

Leecode144題：點選打開連結

vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode *>toVisit;
        vector<int>res;
        if(root==nullptr){
            return res;
        }
        TreeNode *pCurrent=nullptr;
        toVisit.push(root);
        while(!toVisit.empty()){
            pCurrent=toVisit.top();
            res.push_back(pCurrent->val);
            toVisit.pop();
            if(pCurrent->right){
                toVisit.push(pCurrent->right);
            }
            if(pCurrent->left){
                toVisit.push(pCurrent->left);
            }
        }
        return res;
    }