【二叉树】DFS遍历的迭代理解

我们知道，二叉树前中后序遍历的常见写法是递归，而递归的底层逻辑是栈，所以理论上来说，所有递归都能用栈来实现，只是复杂的递归用栈实现起来会很复杂
而这种简单的递归，不仅用栈实现不是很复杂，还涉及到了递归的底层逻辑的理解，是面试很喜欢的题目
现在和我一起走进它吧

如果我们想得到遍历结果，肯定是以某种顺序将节点压入栈中，以某种顺序弹出节点，而弹出节点的顺序就是遍历的结果（出栈的顺序就是遍历结果的顺序）
所以我们要解决的问题就是上方提到的两个某种顺序

先说结论：
前序遍历：结果需要以中左右弹出栈，所以 以中右左的顺序入栈
后序遍历：修改前序遍历的代码两处
中序遍历：用指针记录遍历顺序，到某种程度出栈

前序遍历：

我们知道前序遍历的顺序是中->左->右
举个例子：

5 / \ 4 6 / \ 1 2

遍历结果为54126
它具有一个特点：即时性（访问这个元素，就直接输出，再进行下一步）

class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<int> st; if(root==nullptr) return nullptr; st.push(root->val); while(root){ if(root->right) st.push(root->right->val); if(root->left) st.push(rott->left->val); } return res; } };

后序遍历：

后序遍历的顺序是左->右->中
所以从前序到后序只需要修改两步：中左右->中右左->左右中

• 第一步：将左右的访问顺序对调
• 第二步：将结果数组存储的结果倒序输出

class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; if(root!=nullptr) st.push(root); while(!st.empty()){ TreeNode*topNode=st.top(); st.pop(); v.push_back(topNode->val); if(topNode->left!=nullptr){ st.push(topNode->left); } if(topNode->right!=nullptr){ st.push(topNode->right); } } reverse(v.begin(),v.end()); return v; } };

中序遍历：

后序遍历的顺序是左->中->右
它是特殊的，因为它与我上方说的即时性相反，具有延后性
（访问到这个元素，需要等到它的左子树访问到的时候，才能输出这个元素）
所以我们需要一个指针来记录遍历顺序，当左为空，就弹出该节点；右为空，说明是叶子结点，弹出该节点的父节点

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> v; TreeNode*p=root; while(p!=nullptr||!st.empty()){ if(p!=nullptr){ st.push(p); p=p->left; } else{ p=st.top(); st.pop(); v.push_back(p->val); p=p->right; } } return v; } };