济南川芎网站建设公司,无锡工厂网站建设,长沙最新招聘,wordpress移动端分享插件文章目录 1. 二叉树前序遍历#xff08;迭代法#xff09;2. 二叉树后序遍历#xff08;迭代法#xff09;3. 二叉树中序遍历#xff08;迭代法#xff09; 1. 二叉树前序遍历#xff08;迭代法#xff09;
题目连接 #x1f34e;因为处理顺序和访问顺序是一致的。所… 文章目录 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:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st; // 栈后进先出满足递归想要获取上一个位置的逻辑vectorint 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:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st; // 栈后进先出满足递归想要获取上一个位置的逻辑vectorint 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:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st; // 栈后进先出满足递归想要获取上一个位置的逻辑vectorint 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;}
};
