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

递归遍历

递归遍历相比中序遍历，调整一下顺序即可

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

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

迭代遍历

<aside> 💡

前序遍历时，对节点的访问与操作在同一步进行，所以每次迭代直接取出栈顶节点进行操作即可（对比中序遍历是直到访问到空节点时才取出栈顶节点进行操作）

</aside>

操作完再将节点的左右节点顺序入栈

vector<int> preorderTraversal(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->right)
			st.push(cur->right);
		if(cur->left)
			st.push(cur->left);
	}
	return ans;
}

迭代遍历——统一写法

vector<int> preorderTraversal(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();
			// 右-左-中顺序入栈
			if (cur->right)
				st.push(cur->right);
			if (cur->left)
				st.push(cur->left);
			st.push(cur);
			st.push(nullptr);		// 中节点后添加标识符
		}
		else {
			st.pop();
			cur = st.top();
			ans.push_back(cur->val);
			st.pop();
		}
	}
	return ans;
}