递归的本质就是压栈、回溯、弹栈，那我们模拟他这个过程。
大概可以写成下面的过程：
- 创建一个栈（可以是数组实现的栈或者使用语言提供的栈数据结构），用于暂存遍历过程中的节点。
- 初始化当前节点为根节点。
- 进入循环，判断条件为当前节点不为空或栈不为空。
- 在循环中，执行以下操作：
- 如果当前节点不为空，将当前节点入栈，并将当前节点指向其左子节点（进入左子树）。
- 如果当前节点为空，说明已经到达左子树的最底部，从栈中取出一个节点，访问该节点，并将当前节点指向其右子节点（进入右子树）。
- 不断重复上述过程，直到当前节点为空且栈为空，完成遍历。
前序：
- 创建一个栈，将根节点入栈。
- 进入循环，判断条件为栈不为空。
- 在循环中，取出栈顶节点，访问该节点，并依次将其右子节点和左子节点入栈。
// 非递归前序遍历函数 void preOrderTraversal(TreeNode* root) { if (root == nullptr) return; stack<TreeNode*> nodeStack; // 创建一个栈用于存储结点 nodeStack.push(root); // 将根结点入栈 while (!nodeStack.empty()) { TreeNode* currentNode = nodeStack.top(); // 取出栈顶结点 nodeStack.pop(); // 弹出栈顶结点 cout << currentNode->val << " "; // 访问当前结点 if (currentNode->right) nodeStack.push(currentNode->right); // 先将右子结点入栈，因为前序遍历的顺序是根-左-右 if (currentNode->left) nodeStack.push(currentNode->left); // 再将左子结点入栈 } }
中序：
- 创建一个栈。
- 从根节点开始，将当前节点和所有左子节点按顺序入栈，直到最左的叶子节点。
- 进入循环，判断条件为当前节点为空且栈为空。
- 在循环中，取出栈顶节点，访问该节点，并将当前节点指向其右子节点
vector<int> inorderTraversal(TreeNode* root) { vector<int> result; // 存放遍历结果的向量 stack<TreeNode*> stack; // 用于模拟递归调用的栈 TreeNode* current = root; // 当前节点 while (current != nullptr || !stack.empty()) { // 将当前节点以及其左子树的所有左节点入栈 while (current != nullptr) { stack.push(current); // 将当前节点入栈 current = current->left; // 移动到左子节点 } // 当左子树为空时，弹出栈顶节点并访问 current = stack.top(); stack.pop(); result.push_back(current->val); // 遍历右子树 current = current->right; } return result; }
后序：
- 创建两个栈。一个栈用于存储节点的顺序，另一个栈用于存储实际的后序遍历结果。
- 将根节点入栈1。
- 进入循环，判断条件为栈1不为空。
- 在循环中，取出栈1的栈顶节点，将该节点入栈2，并依次将其左子节点和右子节点入栈1。
- 重复上述过程直到栈1为空。此时，栈2中存储的就是后序遍历的结果，可以按顺序访问栈2中的节点。
// 非递归后序遍历函数 void postOrderTraversal(TreeNode* root) { if (root == nullptr) return; stack<TreeNode*> nodeStack; // 创建一个栈用于存储结点 TreeNode* prevNode = nullptr; // 记录上一个访问过的结点 while (root || !nodeStack.empty()) { if (root) { nodeStack.push(root); // 将当前结点入栈 root = root->left; // 访问左子结点 } else { TreeNode* topNode = nodeStack.top(); if (topNode->right && topNode->right != prevNode) { root = topNode->right; // 若右子结点存在且未被访问过，则访问右子结点 } else { cout << topNode->val << " "; // 访问当前结点 nodeStack.pop(); // 弹出栈顶结点 prevNode = topNode; // 更新上一个结点为当前结点 } } } }
