二叉樹(shù)的前序遍歷

在不使用遞歸的方式遍歷二叉樹(shù)時(shí)，我們可以使用一個(gè)棧模擬遞歸的機(jī)制。二叉樹(shù)的前序遍歷順序是：根 → 左子樹(shù) → 右子樹(shù)，我們可以先將二叉樹(shù)的左路結(jié)點(diǎn)入棧，在入棧的同時(shí)便對(duì)其進(jìn)行訪問(wèn)，此時(shí)就相當(dāng)于完成了根和左子樹(shù)的訪問(wèn)，當(dāng)左路結(jié)點(diǎn)入棧完畢后再?gòu)臈ｍ斠来稳〕鼋Y(jié)點(diǎn)，并用同樣的方式訪問(wèn)其右子樹(shù)即可。

具體步驟如下：

1. 將左路結(jié)點(diǎn)入棧，入棧的同時(shí)訪問(wèn)左路結(jié)點(diǎn)。
2. 取出棧頂結(jié)點(diǎn)top。
3. 準(zhǔn)備訪問(wèn)top結(jié)點(diǎn)的右子樹(shù)。

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) {		stack<TreeNode*> st; //輔助棧		vector<int> ret; //用于存放前序遍歷的結(jié)果		TreeNode* cur = root;		while (cur || !st.empty())		{			//1、將左路結(jié)點(diǎn)入棧，入棧的同時(shí)訪問(wèn)左路結(jié)點(diǎn)			while (cur)			{				st.push(cur);				ret.push_back(cur->val);				cur = cur->left;			}			//2、取出棧頂結(jié)點(diǎn)			TreeNode* top = st.top();			st.pop();			//3、準(zhǔn)備訪問(wèn)其右子樹(shù)			cur = top->right;		}		return ret; //返回前序遍歷結(jié)果	}};

二叉樹(shù)的中序遍歷

二叉樹(shù)的中序遍歷順序是：左子樹(shù) → 根 → 右子樹(shù)，我們可以先將二叉樹(shù)的左路結(jié)點(diǎn)入棧，當(dāng)左路結(jié)點(diǎn)入棧完畢后，再?gòu)臈ｍ斠来稳〕鼋Y(jié)點(diǎn)，在取出結(jié)點(diǎn)的同時(shí)便對(duì)其進(jìn)行訪問(wèn)，此時(shí)就相當(dāng)于先訪問(wèn)了左子樹(shù)再訪問(wèn)了根，之后再用同樣的方式訪問(wèn)取出結(jié)點(diǎn)的右子樹(shù)即可。

具體步驟如下：

1. 將左路結(jié)點(diǎn)入棧。
2. 取出棧頂結(jié)點(diǎn)top并訪問(wèn)。
3. 準(zhǔn)備訪問(wèn)top結(jié)點(diǎn)的右子樹(shù)。

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) {		stack<TreeNode*> st; //輔助棧		vector<int> ret; //用于存放中序遍歷的結(jié)果		TreeNode* cur = root;		while (cur || !st.empty())		{			//1、將左路結(jié)點(diǎn)入棧			while (cur)			{				st.push(cur);				cur = cur->left;			}			//2、取出棧頂結(jié)點(diǎn)并訪問(wèn)			TreeNode* top = st.top();			st.pop();			ret.push_back(top->val);			//3、準(zhǔn)備訪問(wèn)其右子樹(shù)			cur = top->right;		}		return ret; //返回中序遍歷結(jié)果	}};

二叉樹(shù)的后序遍歷

二叉樹(shù)的后序遍歷順序是：左子樹(shù) → 右子樹(shù) → 根，我們可以先將二叉樹(shù)的左路結(jié)點(diǎn)入棧，當(dāng)左路結(jié)點(diǎn)入棧完畢后，再觀察棧頂結(jié)點(diǎn)，若棧頂結(jié)點(diǎn)的右子樹(shù)為空，或棧頂結(jié)點(diǎn)的右子樹(shù)已經(jīng)被訪問(wèn)過(guò)了，則棧頂結(jié)點(diǎn)可以出棧并訪問(wèn)，若棧頂結(jié)點(diǎn)的右子樹(shù)還未被訪問(wèn)，則用同樣的方式訪問(wèn)棧頂結(jié)點(diǎn)的右子樹(shù)，直到其右子樹(shù)被訪問(wèn)后再訪問(wèn)該結(jié)點(diǎn)，這時(shí)的訪問(wèn)順序遵循了二叉樹(shù)的后序遍歷所要求的順序。

具體步驟如下：

1. 將左路結(jié)點(diǎn)入棧。
2. 觀察棧頂結(jié)點(diǎn)top。
3. 若top結(jié)點(diǎn)的右子樹(shù)為空，或top結(jié)點(diǎn)的右子樹(shù)已經(jīng)訪問(wèn)過(guò)了，則訪問(wèn)top結(jié)點(diǎn)。訪問(wèn)top結(jié)點(diǎn)后將其從棧中彈出，并更新上一次訪問(wèn)的結(jié)點(diǎn)為top。
4. 若top結(jié)點(diǎn)的右子樹(shù)還未被訪問(wèn)，則準(zhǔn)備訪問(wèn)其右子樹(shù)。

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) {		stack<TreeNode*> st; //輔助棧		vector<int> ret; //用于存放后序遍歷的結(jié)果		TreeNode* cur = root;		TreeNode* prev = nullptr; //記錄上一次訪問(wèn)的結(jié)點(diǎn)		while (cur || !st.empty())		{			//1、將左路結(jié)點(diǎn)入棧			while (cur)			{				st.push(cur);				cur = cur->left;			}			//2、取出棧頂結(jié)點(diǎn)			TreeNode* top = st.top();			//3、若取出結(jié)點(diǎn)的右子樹(shù)為空，或右子樹(shù)已經(jīng)訪問(wèn)過(guò)了，則訪問(wèn)該結(jié)點(diǎn)			if (top->right == nullptr || top->right == prev)			{				//訪問(wèn)top結(jié)點(diǎn)后將其從棧中彈出				st.pop();				ret.push_back(top->val);				//更新上一次訪問(wèn)的結(jié)點(diǎn)為top				prev = top;			}			else //4、若取出結(jié)點(diǎn)的右子樹(shù)還未被訪問(wèn)，則準(zhǔn)備訪問(wèn)其右子樹(shù)			{				cur = top->right;			}		}		return ret; //返回后序遍歷結(jié)果	}};

注意： 看動(dòng)圖演示時(shí)請(qǐng)結(jié)合所給代碼，動(dòng)圖是嚴(yán)格按照代碼的邏輯制作的。