二叉树进阶刷题02(非递归的前中后序遍历)

前言

二叉树的前序遍历 中序遍历 后序遍历 用递归实现没啥说的，本片博客介绍使用非递归方式实现这三种遍历，毕竟递归的致命缺点就是栈溢出。

题目

1.144. 二叉树的前序遍历 - 力扣（LeetCode）

先看递归的写法，根 左子树 右子树，把问题一个一个拆分成子问题去解决，那我们非递归就是要用循环去拆解这种子问题的解决。我们可以把递归解决问题分为两个层面，一个就是往下递的时候，也就是我们访问根的时候，如下图

其实这部分实现，我们非递归直接就可以实现，难的就是归的时候，如何访问数据，递归可以复用函数实现，可是非递归不能，只能用循环，那如何保存好数据，模拟实现归的过程呢？使用栈辅助，保存数据。接下来我们再来细分下的递归的顺序，把它分成递和归的两个过程，

其实你细分下也就是，左路节点和访问左子树及它的右子树节点而已，访问左路节点，就是递的过程，访问左子树及他的右子树节点就是归的过程。因此，我们在递的过程就要使用栈记录下这些节点，并把这些节点插入顺序表(题目要求)，在访问完左路节点的时候，取栈里的节点，访问他的右子树，继续循环完成右子树的访问，所以这里的子问题划分是依靠循环访问左路节点完成的。这里需要一个节点遍历整课二叉树，我们把它命名为cur。

代码

  vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;while(cur || !st.empty()){//访问左子树while(cur){v.push_back(cur->val);st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();cur = top->right;}return v;}

这里代码的细节是，两个while循环里的条件，第二个就是cur当前指针存在，才去循环。第一个while循环要求两个条件，一个是cur一个是栈不为空，注意cur指针为空可能是访问到叶子节点，不一定二叉树就访问完了。再访问完左路节点，我们就要取栈里的节点，并且要pop掉，关键点就是这句代码，赋值top的右子树，循环划分子问题。

cur = top->right; //划分子问题

2.94. 二叉树的中序遍历 - 力扣（LeetCode）

中序遍历的非递归实现，和前序遍历没啥区别，他的顺序是 左子树 根 右子树，从递归两个层面分类也是左路节点和访问左子树及他的右子树，只不过我们不能像前序遍历那样直接就插入顺序表，而是先入栈，再要访问右子树的时候，才去栈里的节点，再插入顺序表，就是插入的时机不同。

代码

 vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root;while (cur || !st.empty()) {// 访问左子树while (cur) {st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();v.push_back(top->val);cur = top->right;}return v;}

3.145. 二叉树的后序遍历 - 力扣（LeetCode）

后序遍历，和前序中序遍历再实现细节上是有点区别的。我们先看一下后序遍历的顺序左子树 右子树 根，我们把他分成递归两个过程，会发现他的前面过程只能是入栈，一直不能访问，直到访问完左路节点我们还是不能直接访问栈里的节点，还要取遍历他的右子树，继续入栈，直到他的左右子树访问完我们才能访问根，所以这里总结下也是一个访问时机的问题。不同于中序遍历，他的访问时机比较难处理，我们先看如何判断一个根节点啥时候能访问，按照上面的分析过程，我们会访问到两次，第一次不能访问，第二次再栈里遇到他也不能直接访问而是要访问他的右子树才能访问这个根节点。所以说，他的访问时机和他上一次访问的节点有关，因此我们可以定义一个prev变量，记录上一次访问的节点(就是插入到顺表的节点)

代码

  vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> v;TreeNode* cur = root,*prev = nullptr;while (cur || !st.empty()) {// 访问左子树while (cur) {st.push(cur);cur = cur->left;}TreeNode* top = st.top();//右子树为空 或者 上一个结点是这个结点的右子树的根if(top->right == nullptr || top->right == prev){//访问完 赋值给上一个结点prev = top;st.pop();v.push_back(top->val);}else{cur = top->right;}}return v;}

关键点 如下图代码

            if(top->right == nullptr || top->right == prev){//访问完 赋值给上一个结点prev = top;st.pop();v.push_back(top->val);}else{cur = top->right;}

就是访问时机的判断，一直循环访问左路节点，直到访问为空，退出循环，取出top节点，判断他的右子树是否为空(叶子节点)或者上一个节点就是top节点的右子树的根节点，满足任意一个条件，就插入数据，并且pop栈顶结点，最后不要忘了更新prev指针，如果不是，那就继续访问他的右子树，划分子问题。

总结

这三道题目类似，大致一个思路，只是细节实现上有点区别。其实会了前序，中序和后序就不成问题。不过可能后序上还是有点问题，他这里需要使用一个prev指针记录上一次访问的结点，做访问时机判断，这还是有点难想到的，要多做分析。