👉前言👈
二叉树的前中后遍历如果采取递归的方式来实现，是相当容易的事情。递归之所以强大，是因为有系统自动压栈。那么非递归的前中后序遍历就是借助栈，通过我们自己手动压栈来实现二叉树的遍历。当然除了递归和非递归的遍历方式，还有二叉树的 Morris 遍历，这部分内容也将会在下一篇博客中呈现给大家！那话不多说，直接开整！
👉二叉树的前序遍历👈
给你二叉树的根节点 root ，返回它节点值的前序遍历。
二叉树的非递归前序遍历实现步骤：
首先申请一个栈，如果头节点不为空，将头节点放入栈中。
当栈不为空时，while循环继续以下操作：弹出栈顶节点记为cur，然后对cur进行处理（在本道题中，处理cur的操作是将cur->val插入到vector的尾部）。如果节点cur的左右孩子均不为空，先将右孩子压入栈中，再将左孩子压入栈中。注意：如果孩子为空，就不需要压入栈中。
回到第 2 步，继续进行while循环判断。循环结束后，vector中存储的就是二叉树的前序遍历。
为了验证以上步骤的正确性，我为大家举了一个例子。见下图所示：
为什么以上过程就能够得到正确的前序遍历呢？因为入栈顺序是头、右、左，那么出栈顺序就是头、左、右（中序遍历的顺序）。注：出栈的顺序并不是左、右、头，因为头节点入栈后就出栈了，而左孩子出栈后，左孩子的左孩子和右孩子也要进栈，那么右孩子就被压在栈底了，并不是马上就能访问到它。
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> ret; if(root != nullptr) { // 头节点不为空,头节点先入栈 stack<TreeNode*> st; st.push(root); // 栈不为空,while循环继续 while(!st.empty()) { // 弹出栈顶节点 TreeNode* cur = st.top(); st.pop(); // 处理cur ret.push_back(cur->val); // 右孩子先入栈,左孩子后入栈 if(cur->right != nullptr) { st.push(cur->right); } if(cur->left != nullptr) { st.push(cur->left); } } } return ret; } };
👉二叉树的后序遍历👈
给定一个二叉树的根节点 root ，返回 它的后序遍历 。
二叉树的非递归后序遍历实现步骤：
首先申请两个栈，一个为辅助栈st1，另一个为收集栈st2。如果头节点不为空，将头节点压入辅助栈st1中。
当辅助栈st1不为空时，while循环继续以下操作：弹出栈顶节点记为cur，然后将cur压入收集栈st2中。如果节点cur的左右孩子均不为空，先将左孩子压入辅助栈st1中，再将右孩子压入辅助栈st1中。注意：如果孩子为空，就不需要压入栈中。
回到第 2 步，继续while循环判断。循环结束后，再将收集栈st2中的节点依次弹出就能够得到后序遍历的结果了。
为何以上步骤就能够得到正确的后序遍历结果呢？因为入辅助栈的顺序是头、左、右，那么出辅助栈的顺序是头、右、左（理由同前序遍历）。而出辅助栈的顺序就是入收集栈的顺序，即如收集栈的顺序就是头、右、左，所以出收集栈的顺序就是左、有、头（后序遍历的顺序）。注：收集栈是将全部节点收集完才依次出栈的，并不像辅助栈那样边出栈边入栈。如果还是不了解以上过程的，大家可以按照以上过程画一遍图，那么就会对以上过程会有更深的理解了。
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> ret; if(root != nullptr) { stack<TreeNode*> st1; // 辅助栈 stack<TreeNode*> st2; // 收集栈 // 头节点先入辅助栈 st1.push(root); while(!st1.empty()) { TreeNode* cur = st1.top(); st1.pop(); // cur压入收集栈中 st2.push(cur); // 先将左孩子压入辅助栈,再将右孩子压入辅助栈 if(cur->left != nullptr) { st1.push(cur->left); } if(cur->right != nullptr) { st1.push(cur->right); } } // 收集结果 while(!st2.empty()) { ret.push_back(st2.top()->val); st2.pop(); } } return ret; } };
👉二叉树的中序遍历👈
给定一个二叉树的根节点 root ，返回 它的中序遍历 。
二叉树的非递归后序遍历实现步骤：
如果头节点不为空，则申请一个栈和一个指针变量TreeNode* cur并且头节点的左边界上的节点依次进栈。
当栈不为空或者cur不为空时，while循环继续一下操作：弹出栈顶节点赋值给cur，然后对cur进行处理（在本道题中，处理cur的操作是将cur->val插入到vector的尾部）。如果cur有右子树，则将右子树左边界上的节点依次压入栈中。
回到第 2 步，继续while循环判断。循环结束后，就能得到中序遍历的结果。
为什么按照以上步骤就能够得到正确的中序遍历呢？因为每一课二叉树都可以被左边界分解掉。入栈的顺序是头、左，出栈的顺序是左、头，且让左孩子的右子树的左边界入栈。那么出栈的顺序就是左、头、右了，也就是中序遍历的顺序。
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> ret; if(root != nullptr) { stack<TreeNode*> st; TreeNode* cur = root; while(!st.empty() || cur != nullptr) { // 左边界入栈 if(cur != nullptr) { st.push(cur); cur = cur->left; } else // 到达左边界的空节点了 { // 弹出栈顶节点 cur = st.top(); st.pop(); ret.push_back(cur->val); // 如果右子树不为空,则下一次循环右子树的左边界会进栈 cur = cur->right; } } } return ret; } };
👉总结👈
本篇博客主要讲解了二叉树的非递归式前中后序遍历。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
