4.1深度优先遍历的迭代方式

leetcode :
144.二叉树的前序遍历
94.二叉树的中序遍历
145.二叉树的后序遍历

递归的实现：
每一次调用递归： 都会将函数在本次递归中所产生的局部变量， 参数值 和返回地址等压入调用栈中；
递归返回时： 从栈顶 弹出上一次递归的各项参数， 所以递归可以返回上一层的位置；

从而我们知道， 栈可以实现二叉树的递归方式；
同样，我们本次使用栈 实现二叉树的 迭代方式；

使用迭代方式的遍历过程中， 有两关键点：

1. 访问节点（ 将节点压入栈中）；
2. 处理节点（将节点从栈中取出， 然后将节点中的数据部分存入到结果集中）；

整体思路：
前序，后序遍历， 先将根节点入栈，
接着循环中，是先处理节点，然后开始访问节点；

中序遍历： 先将当前节点赋值为根节点；
在循环中， 先处理栈中节点， 将节点中的数据存到结果集中， 然后才开始 访问节点；

1. 前序遍历的迭代方式

1. 由于栈的后进先出的特性；

2. 前序遍历的输出顺序是： 中，左，右；

根据以上两点，可知：
所以入栈的 顺序： 中 ，右 ， 左， 中 ；

1.1 步骤

创建 结果集 向量容器, result；
创建 节点型 stack 容器适配器， st;

条件判断， 当根节点为空， 返回结果集；
将根节点 压入到栈中；

执行循环， 当栈不为空：

         新建当前节点， 赋值为栈顶的节点的引用；
         移除栈顶节点；
         将当前节点中的数值保存到结果集中；
         条件判断， 当前节点的右节点不为空， 将当前节点的右节点压入栈中；
         条件判断， 当前节点的左子树不为空，  将当前节点的左节点压入到栈中；

循环结束， 返回结果集；

1.2 code

#include "vector"
#include "stack"

using namespace std;

struct TreeNode{
    int val;
    TreeNode*  left;
    TreeNode*  right;

    // 默认构造函数， 列表形式；
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}

};

class Solution1{

    vector<int>  preOrder(TreeNode* root) {

        vector<int> result;
        stack<TreeNode*> st;
        // 当根节点为空时， 返回结果集;
        if( root == nullptr )  return  result;
        // 根节点不为空，压入栈中；
        st.push(root);

        while( !st.empty()){
            TreeNode*  cur_node = st.top();  //  当前节点 赋值为 栈顶的节点；
            // 移除栈顶节点；
            st.pop();
            result.push_back(cur_node->val);
            if(cur_node->right)  st.push(cur_node->right);
            if(cur_node->left)  st.push(cur_node->left);
        }
        return  result;
    }
};

关键点：

1. 处理： 将元素放进result 数组中；
2. 访问： 遍历节点；

前序遍历中： 先访问的是中间节点， 要处理的元素也是中间节点； 即， 访问的元素和 要处理的元素顺序是一致的，都是中间节点；

2. 中序遍历的迭代方式

中序遍历： 左，中， 右； 先访问根节点， 然后一层一层的向下访问， 直到到达树左边的最底部， 在开始处理节点，造成了处理顺序和访问顺序不一致的；

故

1. 访问节点： 使用指针来遍历；
2. 处理节点： 使用栈来处理；

关键点：
先访问节点， 直到当前节点更新为空节点；
开始处理节点；

2.1 步骤

创建 结果集 向量容器, result；
创建 节点型 stack 容器适配器， st;
令当前节点 赋值为 根节点；

执行循环， 当 当前节点不为空， 或者 栈不为空：
条件判断： 当前节点 不为空，
将当前节点压入栈；
当前节点更新为 当前节点的左节点；
否则， 当前节点为空：
当前节点赋值为 栈顶的节点引用；
移除栈顶的节点；
将当前节点中的 数值存入到 结果集中；
当前节点 更新为 当前节点的右节点；

循环结束， 返回结果集；

class Solution2{
public:
    vector<int>  inOrder(TreeNode* root) {

        vector<int> result;  // 用于 处理节点， 将节点中的数值保存其中；
        stack<TreeNode *> st;  // 用于访问节点时， 将节点入栈；

        TreeNode* cur_node = root;

        // 开始遍历 树的节点和栈中的节点；
        while(  cur_node != nullptr||  !st.empty()  ) {
            // 循环， 当前节点不为空， 访问没到到位，未到叶子节点；  栈不为空， 处理没有到位；
            // 先进行访问；
            if( cur_node != nullptr){ // 如果当前节点未到达， 叶子节点；
                // 依次 将访问的节点入栈；
                st.push(cur_node);
                cur_node = cur_node->left; //  将访问节点 更新为 当前节点的左子树；
            }else{ // 访问结束， 开始处理节点；
                cur_node = st.top(); // 返回栈顶元素的引用；
                result.push_back(cur_node->val);  //  处理节点， 节点中的元素入栈；
                st.pop();
                cur_node = cur_node->right;
            }
        }
        return  result;
    }

};

3. 后序遍历的迭代方式

前序： 入栈顺序， 中， 右， 左； 结果集中的元素： 中， 左， 右；

后序：

后序遍历， 是在前序遍历的 基础上，进行两点修改：

1. 节点入栈的顺序改变；
2. 结果集中的 元素，需要倒序一下；

3.1 步骤

创建 结果集 向量容器, result；
创建 节点型 stack 容器适配器， st;

条件判断， 当根节点为空， 返回结果集；
将根节点 压入到栈中；

执行循环， 当栈不为空：

         新建当前节点， 赋值为栈顶的节点的引用；
         移除栈顶节点；
         将当前节点中的数值保存到结果集中；
         条件判断， 当前节点的右节点不为空， 将当前节点的右节点压入栈中；
         条件判断， 当前节点的左子树不为空，  将当前节点的左节点压入到栈中；

反转结果集，
循环结束， 返回结果集；

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
          vector<int>  result;
          stack<TreeNode* >  st;

          if(root == nullptr)  return  result;   // 根节点为空， 返回结果集；
          st.push(root) ;  // 先将根节点入栈；

          while( !st.empty() ){// 当 栈中的节点不为空时，
              //  取出栈顶节点，进行处理；
              TreeNode* cur_node =  st.top();
              result.push_back(cur_node->val);
              st.pop();

              // 访问节点；
              if(cur_node->left)  st.push( cur_node->left);
              if(cur_node->right) st.push( cur_node->right);

          }

          reverse(result.begin(), result.end());
          return result;
      }

};

这篇好文章是转载于：学新通技术网