迭代实现二叉树深度优先遍历（前序遍历，中序遍历，后序遍历）

二叉树结构体定义：

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 preorderTraversal(TreeNode* root) {
		vector result;
		stack stk;
		if (root == nullptr) return result;
		stk.push(root);
		while (!stk.empty()) {
			TreeNode* tempNode = stk.top();
			stk.pop();
			result.push_back(tempNode->val);
			if (tempNode->right) {
				stk.push(tempNode->right);
			}
			if (tempNode->left) {
				stk.push(tempNode->left);
			}
		}
		return result;
	}
};

二叉树中序遍历：

class Solution {	//二叉树的中序遍历 迭代
public:
	vector inorderTraversal(TreeNode* root) {
		vector result;
		stack stk;
		TreeNode* cur = root;
		while (!stk.empty() || cur!=nullptr) {
			if (cur != nullptr) {	//左 访问到最底层
				stk.push(cur);
				cur = cur->left;
			}
			else {
				cur = stk.top();
				stk.pop();
				result.push_back(cur->val);	//中
				cur = cur->right;	//右
			}
		}
		return result;
	}
};

二叉树后序遍历：

class Solution {	//二叉树的后序遍历 迭代
public:
	vector postorderTraversal(TreeNode* root) {
		vector result;
		stack stk;
		if (root == nullptr) return result;
		stk.push(root);
		while (!stk.empty()) {
			TreeNode* tempNode = stk.top();
			stk.pop();
			result.push_back(tempNode->val);
			if (tempNode->left) {
				stk.push(tempNode->left);
			}
			if (tempNode->right) {
				stk.push(tempNode->right);
			}
		}
		reverse(result.begin(), result.end());
		return result;
	}
};

主函数：

int main() {
	TreeNode* p5 = new TreeNode(5);
	TreeNode* p4 = new TreeNode(4);
	TreeNode* p3 = new TreeNode(3);
	TreeNode* p2 = new TreeNode(2, p4, p5);
	TreeNode* p1 = new TreeNode(1, p2, p3);
	Solution s;
	vector result = s.preorderTraversal(p1);//前序
	//vector result = s.inorderTraversal(p1);//中序
	//vector result = s.postorderTraversal(p1);//后序
	for (int i : result) {
		cout << i << "t";
	}
	cout << endl;
	return 0;
}

参考资料：代码随想录