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í)訪問左路結(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)備訪問其右子樹
			cur = top->right;
		}
		return ret; //返回前序遍歷結(jié)果
	}
};

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)并訪問
			TreeNode* top = st.top();
			st.pop();
			ret.push_back(top->val);
			//3、準(zhǔn)備訪問其右子樹
			cur = top->right;
		}
		return ret; //返回中序遍歷結(jié)果
	}
};

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; //記錄上一次訪問的結(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)的右子樹為空，或右子樹已經(jīng)訪問過了，則訪問該結(jié)點(diǎn)
			if (top->right == nullptr || top->right == prev)
			{
				//訪問top結(jié)點(diǎn)后將其從棧中彈出
				st.pop();
				ret.push_back(top->val);
				//更新上一次訪問的結(jié)點(diǎn)為top
				prev = top;
			}
			else //4、若取出結(jié)點(diǎn)的右子樹還未被訪問，則準(zhǔn)備訪問其右子樹
			{
				cur = top->right;
			}
		}
		return ret; //返回后序遍歷結(jié)果
	}
};