二叉樹經典題之二叉樹的非遞歸周遊

文章目錄

• 前序周遊非遞歸
• • 思路
  • 代碼
  • 其他寫法
• 中序周遊非遞歸
• • 思路
  • 代碼
• 後序周遊非遞歸
• • 思路
  • 代碼
  • 更為簡單的寫法

前序周遊非遞歸

題目連結：LeetCode：前序周遊非遞歸

思路

讓左節點不斷入棧，入棧就代表通路（在題目中對應的就是将元素壓入vector中），當走到最左側時停止入棧，此時現在的任務就是處理右子樹了。是以開始出棧，每出棧一個元素檢視其是否存在右子樹，如果沒有右子樹那麼繼續出棧，如果存在右子樹，這表示來了一個新的子樹，那麼對于這顆子樹隻需作為子問題重複執行即可

代碼

*/
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> s;
        TreeNode* cur=root;
        while(cur || !s.empty())
        {
            //首先讓這顆樹的左節點一直入棧
            while(cur)
            {
                ret.push_back(cur->val);
                s.push(cur);
                cur=cur->left;
            }
            //當停止時表示到了這棵樹的最左結點，那麼此時出棧看一下是否存在右子樹
            //如果不存在子樹那麼cur就是null，也就是會繼續出下一個結點
            //如果存在子樹，那麼cur就會作為子問題去處理其右子樹
            TreeNode* temp=s.top();
            s.pop();
            
            cur=temp->right;
            
        }
        return ret;
    }
};
           

其他寫法

關于前序周遊其實還有另外一種比較流行的寫法，但是這種寫法不推薦使用，因為它和我們上面的思路有點不相符合，掌握上面的思路後也可以适用于後序和中序周遊的非遞歸

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> s;
        if(root)
        {
            s.push(root);
            while(!s.empty())
            {
                TreeNode* p=s.top();
                s.pop();
                ret.push_back(p->val);//前序周遊進棧時做通路結點的操作
                
                if(p->right)//先入右節點，因為先序周遊先要通路左節點
                {
                    s.push(p->right);
                }
                if(p->left)
                {
                    s.push(p->left);
                }
            }
        }
        return ret;
    }
};

           

中序周遊非遞歸

題目連結：LeetCode：中序周遊非遞歸

思路

依舊采用前序周遊非遞歸的第一種思路，代碼也僅僅有很小的差別。在中序周遊非遞歸中，要一直先進棧，但進棧的時候不做通路結點的操作，一直到最左面結點時出棧，出棧時通路，通路完畢之後再看其是否有子樹，如果有的話繼續處理其子樹，也就是子問題

代碼

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> s;
        TreeNode* cur=root;
        while(cur || !s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            
            TreeNode* temp=s.top();
            s.pop();
            ret.push_back(temp->val);//中序周遊出棧時做通路結點的操作
            
            cur=temp->right;
        }
        return ret;
    }
};
           

後序周遊非遞歸

題目連結：LeetCode：後序周遊非遞歸

思路

後序周遊有一些細節需要注意，後序周遊由于是最後才通路根節點，是以根節點勢必會經過兩次，第一次經過時是判斷其是否擁有右子樹，如果有的話，第二次經過時顯然是右子樹已經通路完畢了，是以在這裡必須要進行合理的判斷，否則就會出現死循環

此題中可以定義一個指針prev，在準備pop時，看一下目前棧頂結點的右節點是否被通路過

代碼

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root)
    {
        vector<int> ret;
        stack<TreeNode*> s;
        TreeNode* cur=root;
        TreeNode* prev=nullptr;
        while(cur || !s.empty())
        {
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            
            TreeNode* temp=s.top();
            //拿到結點後先不要出棧，需要進行判斷
            //如果右子樹為空，或者說取出的這個節點的右子樹已經通路完畢了，那麼就通路該根節點
            if(temp->right==nullptr || temp->right==prev)
            {
                ret.push_back(temp->val);
                s.pop();
                
                prev=temp;//該根節點有可能還是其他結點的右節點
                cur=nullptr;
            }
            else
            {
                //如果右子樹不為空，或者沒有通路，那麼繼續子問題
                cur=temp->right;
            }
        }
        return ret;
    }
};
           

更為簡單的寫法

上面的寫法隻是為了很好的了解後序周遊，其實我們隻需對前序周遊非遞歸稍加改動即可完成後序周遊的非遞歸寫法

後序周遊是“左-右-根”，而前序周遊是“根-左-右”，如果将前序周遊變為“根-右-左”，然後反轉豈不是就達到了目的？其實“根-右-左”這種周遊方式我們稱之為逆後序周遊。是以這也就意味着隻需将前序周遊改為先右後左，然後再反轉vector即可

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        stack<TreeNode*> s;
        TreeNode* cur=root;
        while(cur || !s.empty())
        {
            while(cur)
            {
                ret.push_back(cur->val);
                s.push(cur);
                cur=cur->right;//先右
            }
            TreeNode* temp=s.top();
            s.pop();
            
            cur=temp->left;//後左
            
        }
        reverse(ret.begin(),ret.end());//反轉
        return ret;
    }
};