文章目錄

• 前序遍歷非遞歸
• • 思路
  • 代碼
  • 其他寫法
• 中序遍歷非遞歸
• • 思路
  • 代碼
• 后序遍歷非遞歸
• • 思路
  • 代碼
  • 更為簡單的寫法

前序遍歷非遞歸

題目鏈接：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;} };

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的二叉树经典题之二叉树的非递归遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。