算法力扣刷題三十六【二叉樹迭代遍歷】

前言

記錄三十五介紹了二叉樹基礎，和遞歸法模版及遍歷方式；
遞歸：代碼簡單，但要想清楚三步：

確定參數和返回值；
確定終止條件，并return什么？；
終止條件外的邏輯，在哪里做到自己調用自己？——應該是出現嵌套時候，要重復操作的時候。

遞歸的問題：遞歸次數多，開的新棧多，內存空間占用大。

如果二叉樹前中后序遍歷使用非遞歸方法，怎么操作？

一、“輸入”學習階段

學習參考鏈接

解釋迭代

重復執行一段代碼，直到滿足某個條件后停止。用循環可以實現重復；（遞歸也是重復）。

前序遍歷

過程

模擬遞歸過程，用結構棧。

先把根節點放到棧中，再取出根節點加入遍歷數組；
先放入右孩子，再放入左孩子。（左孩子先出來，說明先處理左子樹）。
直到棧為空。
總結：取出根節點，拿右孩子和左孩子入棧交換。先訪問到中節點，可以直接處理中節點；再訪問到左孩子（后入棧），處理左子樹；再訪問到右孩子（先入棧），處理右子樹。訪問節點順序=處理節點順序。

代碼實現

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* cur = st.top();st.pop();if(cur != nullptr){result.push_back(cur->val);st.push(cur->right);	//如果cur是葉子節點，把空也入棧，但是取到空的時候不操作。st.push(cur->left);}}return result;}
};

上面的實現：把葉子結點的左右孩子是空，也入棧，但是不操作。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root == nullptr) return result;st.push(root);while(!st.empty()){TreeNode* cur = st.top();st.pop();result.push_back(cur->val);if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left);}return result;}
};

這是參考代碼，空就不入棧，所以可以在pop之后直接push_back。

后序遍歷

過程

前序實現得到：中左右；
如果先放左孩子，再放右孩子；得到中右左；
把result最后整體reverse，得到左右中。
總結：先訪問到中節點，可以直接處理中節點；再訪問到右孩子（后入棧），處理右子樹；再訪問到左孩子（先入棧），處理左子樹。訪問節點順序=處理節點順序。最后reverse結果。

代碼實現

參考代碼：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode* > st;if(root == nullptr) return result;st.push(root);while(!st.empty()){TreeNode* cur = st.top();st.pop();result.push_back(cur->val);if(cur->left) st.push(cur->left);if(cur->right) st.push(cur->right);}reverse(result.begin(),result.end());return result;}
};

中序遍歷

過程

有所區別原因：訪問節點順序不等于處理節點順序。每一次先接觸中間節點，但不能處理它，要找它的左子樹；找到左子樹，再處理它；再找右子樹。

用棧來記錄遍歷過的元素，雖然訪問到但是還沒到要處理的時候。
cur != 空，作為中節點，放入棧中；cur = cur->left;把left給到下一棒。
如果遇到空，說明左子樹結束；需要從棧中取元素，放入result，st.pop（）；cur = cur->right;再把right給到下一棒。
當cur == 空且st棧為空，終止。cur==空，說明訪問結束；st等于空，說明沒有中節點可以取。

代碼實現

根據思路，先自我實現：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root == nullptr) return result;st.push(root);TreeNode* cur = root->left;while(1){if(cur != nullptr){st.push(cur);cur = cur->left;}else{if(st.empty()) break;cur = st.top();st.pop();result.push_back(cur->val);cur = cur->right;}}return result;}
};

對照參考代碼：
去掉 if(st.empty()) break; while條件改為（cur != nullptr || !st.empty()）

二、統一迭代遍歷實現

學習參考鏈接

思路學習

標記法

將訪問的節點放入棧中，把要處理的節點也放入棧中但是標記要處理的節點。
如何標記？要處理的節點放入棧之后，緊接著放入一個空指針作為標記。

代碼實現

前序遍歷：中左右。所以cur不為空時，入棧順序：右左中。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root != nullptr) {st.push(root);}while(!st.empty()){TreeNode* cur = st.top();if(cur != nullptr){st.pop();if(cur->right) st.push(cur->right);//先放入右孩子if(cur->left) st.push(cur->left); //再放入左孩子st.push(cur);   //放入中節點，緊跟著NULL，代表處理過，它下一輪該進resultst.push(nullptr);}else{st.pop();   //把空指針先彈出TreeNode* temp = st.top();//獲取入數組的元素st.pop();   //彈出該元素result.push_back(temp->val); }}return result;}
};

中序遍歷：左中右。所以cur不為空時，入棧順序：右中左。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root != nullptr) {st.push(root);}while(!st.empty()){TreeNode* cur = st.top();if(cur != nullptr){st.pop();if(cur->right) st.push(cur->right);//先放入右孩子st.push(cur);   //放入中節點，緊跟著NULL，代表處理過，它下一輪該進resultst.push(nullptr);if(cur->left) st.push(cur->left); //再放入左孩子}else{st.pop();   //把空指針先彈出TreeNode* temp = st.top();//獲取入數組的元素st.pop();   //彈出該元素result.push_back(temp->val); }}return result;}
};

后序遍歷：左右中。所以cur不為空時，入棧順序：中右左。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root != nullptr) st.push(root);while(!st.empty()){TreeNode* cur = st.top();if(cur != nullptr){st.push(nullptr);	//先放中節點，直接放null，標記下if(cur->right) st.push(cur->right);//再放右孩子if(cur->left) st.push(cur->left);//再放左孩子}else{st.pop();TreeNode* temp = st.top();st.pop();result.push_back(temp->val);}}return result;}
};

總結

本文學習迭代遍歷二叉樹。用循環+棧處理。

非統一的方法：
- 前序遍歷：根節點先入棧，每出棧一個根節點，就把右左孩子放入。相當于交換。
- 后序遍歷：中左右——中右左——左右中；
- 中序遍歷：棧放遍歷的元素，不為空，把left交到下一棒；為空，取出中節點；把right交到下一棒。
統一方法：標記法。要處理的節點后面緊跟著是null，取到棧頂是空，代表要入棧。直到整個棧空。
- 前序遍歷：不為空，放入順序：右左中；
- 中序遍歷：不為空，放入順序：右中左；
- 后序遍歷：不為空，放入順序：中右左；

（歡迎指正，轉載標明出處）