成都网络优化网站个人建 行业 网站

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;}
};