https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

同前序遍历，递归遍历与迭代遍历的统一写法都只需要改变一下节点压入栈的顺序即可

递归遍历

void traversal(TreeNode* root, vector<int>& ans) {
	if (root == nullptr)
		return;
	traversal(root->left, ans);
	traversal(root->right, ans);
	ans.push_back(root->val);
}

vector<int> postorderTraversal(TreeNode* root) {
	vector<int> ans;
	traversal(root, ans);
	return ans;
}

迭代遍历

后序遍历只需将前序遍历时左右入栈的顺序交换一下（变为中-右-左），最后将结果数组反转即可（中-右-左反转变为左-右-中，即后序遍历的顺序）

vector<int> postorderTraversal(TreeNode* root) {
	vector<int> ans;
	if (!root)
		return ans;
	stack<TreeNode*> st;
	TreeNode* cur;

	st.push(root);
	while (!st.empty()) {
		// 先以中右左的顺序存入数组
		// 中
		cur = st.top();
		st.pop();
		ans.push_back(cur->val);
		// 右、左
		if (cur->left)
			st.push(cur->left);
		if (cur->right)
			st.push(cur->right);
	}
	// 再将数组反转，中右左 变为 左右中，即后序遍历顺序
	std::reverse(ans.begin(), ans.end());
	return ans;
}

迭代遍历——统一写法

vector<int> postorderTraversal(TreeNode* root) {
	vector<int> ans;
	stack<TreeNode*> st;
	TreeNode* cur;
	if (root)
		st.push(root);

	while (!st.empty()) {
		cur = st.top();
		if (cur) {
			st.pop();
			// 中-右-左顺序入栈
			st.push(cur);
			st.push(nullptr);		// 中节点后添加标识符
			if (cur->right)
				st.push(cur->right);
			if (cur->left)
				st.push(cur->left);
		}
		else {
			st.pop();
			cur = st.top();
			ans.push_back(cur->val);
			st.pop();
		}
	}
	return ans;
}