当前位置：首页 > news >正文

【代码随想录二叉树】二叉树前序、中序、后序遍历的迭代遍历

news 2025/7/23 21:34:18

文章目录

- - 1. 二叉树前序遍历（迭代法）
  - 2. 二叉树后序遍历（迭代法）
  - 3. 二叉树中序遍历（迭代法）

1. 二叉树前序遍历（迭代法）

题目连接

在这里插入图片描述

🍎因为处理顺序和访问顺序是一致的。所以方便处理！

示例代码如下所示：

/*** Definition for a binary tree node.* 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> ans;if (root == nullptr)return ans;st.push(root);while (!st.empty()){TreeNode* node = st.top();ans.push_back(node->val);st.pop();// 为什么先弹入右节点呢 ？ （因为栈是后进先出的）if (node->right != nullptr){st.push(node->right);}if (node->left != nullptr){st.push(node->left);}}return ans;}
};

2. 二叉树后序遍历（迭代法）

题目链接🔗
在这里插入图片描述

在这里插入图片描述

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;    // 栈：后进先出，满足递归想要获取上一个位置的逻辑vector<int> ans;if (root == nullptr)return ans;st.push(root);while (!st.empty()){TreeNode* node = st.top();ans.push_back(node->val);st.pop();//只需要改一下左右子树的遍历顺序即可if (node->left != nullptr){st.push(node->left);}if (node->right != nullptr){st.push(node->right);}}reverse(ans.begin(), ans.end());return ans;}
};

3. 二叉树中序遍历（迭代法）

题目链接🔗

在这里插入图片描述

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;    // 栈：后进先出，满足递归想要获取上一个位置的逻辑vector<int> ans;if (root == nullptr)return ans;st.push(root);while (!st.empty()){TreeNode* node = st.top();ans.push_back(node->val);st.pop();if (node->left != nullptr){st.push(node->left);}if (node->right != nullptr){st.push(node->right);}}reverse(ans.begin(), ans.end());return ans;}
};