二叉樹的周遊 非遞歸實作 棧 c++

一、對于一棵二叉樹的而言，最普遍的操作就是進行周遊，周遊又分先序周遊，中序周遊，後序周遊，層序周遊。本次部落客要是針對前面三種周遊方式，一般的方法就是采用遞歸，即逐個根節點進行遞歸操作，那麼如何采用非遞歸進行周遊呢，這裡就需要借助于棧這種資料結構。

二、下面以具體的題目及代碼進行講解（題目是leetcode線上程式設計）

1.求給定的二叉樹的前序周遊

這裡以具體的例子進行講解

定義一個棧和輸出序列容器，循環結束條件是棧為空且根結點為空，這表示已經周遊結束了。開始根結點5不為空進入循環，輸出5的value值，5進棧，此時root變為5的左子樹4，同理1進棧

此時s包含 1 4 5（1為棧頂）

1的左子樹為空，則進入判斷，如果棧非空，則彈出1開始周遊右子樹，此時右子樹為空，則傳回到4，周遊4的右子樹。重複操作最後輸出先序周遊。

vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        /*
        //遞歸
        if(root==NULL)
            return res;
        else{
            res.push_back(root->val);
            preorderTraversal(root->left);
            preorderTraversal(root->right);
        }
        return res;*/
        //非遞歸 棧
        stack<TreeNode*>s;
        vector<int>reg;
        if(root==NULL)
            return reg;
        while(!s.empty()||root!=NULL){
            while(root!=NULL){
                reg.push_back(root->val);
                s.push(root);
                root=root->left;
            }
            if(!s.empty()){
                TreeNode* temp=s.top();
                s.pop();
                root=temp->right;
            }
        }
        return reg;
    }
           

2.給出一棵二叉樹，傳回這棵樹的中序周遊

中序周遊與先序周遊基本相同，隻是輸出value值的語句位置不同而已。

vector<int> inorderTraversal(TreeNode* root) {
        // write code here
        /*
        //複習遞歸
        if(root==NULL)
            return vec;
        else{
            inorderTraversal(root->left);
            vec.push_back(root->val);
            inorderTraversal(root->right);
        }
        return vec;*/
        
        //非遞歸
        vector<int>vec;
        if(root==NULL)
            return vec;
        stack<TreeNode*>s;
        while(!s.empty()||root!=NULL){
            while(root!=NULL){
                s.push(root);
                root=root->left;
            }
            if(!s.empty()){
                TreeNode* temp=s.top();
                s.pop();
                vec.push_back(temp->val);
                root=temp->right;
            }
        }
        return vec;
    }
           

3.求給定的二叉樹的後序周遊

vector<int> postorderTraversal(TreeNode* root) {
        // write code here
        /*if(root!=NULL){
            postorderTraversal(root->left);
            postorderTraversal(root->right);
            vec.push_back(root->val);
        }
        return vec;*/
        vector<int>vec;
        if(root==NULL)
            return vec;
        stack<TreeNode*>s;
        while(root!=NULL||!s.empty()){
            while(root!=NULL){
                s.push(root->left);
                vec.push_back(root->val);
                root=root->right;
            }
            root=s.top();
            s.pop();
        }
        reverse(vec.begin(),vec.end());
        return vec;
        
    }