[算法]二叉树的非递归遍历算法

1.二叉树的非递归中序遍历算法

二叉树的中序遍历方法是：左中右，因此一开始会顺着根节点的左孩子一直往下（这点和先序遍历一样，这也是二者前面部分代码很相似的原因），到最后一个左孩子时尝试把它的右孩子塞进栈内，然后顺着它的的左孩子而下，直到不能访问为止。利用的栈FILO的特性，对每个节点都进行顺左孩子而下即可。

上代码：

 1   void inOrder(TreeNode* root,vector<int>& inOrder)
 2   {
 3     stack<TreeNode*>st;
 4     TreeNode* p = root;
 5     while (p != nullptr || !st.empty())
 6     {
 7       while (p != nullptr)
 8       {
 9         st.push(p);
10         p = p->left;
11       }
12       if (!st.empty())
13       {
14         auto top = st.top();
15         inOrder.push_back(top->val);
16         st.pop();
17         p = top->left;
18       }
19     }
20   }

2。二叉树的层次遍历

思路：即每层遍历，利用队列FIFO特性，每当遍历每层第一个元素时把它的子节点插入队列，那么它也会时下一层第一个遍历的。

int levelOrder(Node* root，vector<int>vecLevel) 
    {
      if(root!=nullptr)
      {
        queue<Node*> q;
        q.push(root);
        while(!q.empty())
        {
          auto front = q.front();
          vecLevel.push_back(front);
          q.pop();
          if(front->left!=nullptr)
            q.push(front->left);
          if(front->right!=nullptr)
            q.push(front->right);
          }
        }
      }
    }

3.二叉树的先序遍历

思路：二叉树的先序遍历即根→左→右，那么遍历时会沿着根节点的左孩子而下直到最底层的左孩子，然后立即访问当前最底层左孩子的右子树，当访问完，即返回上一层的左孩子节点，然后访问其右子树。

 1 vector<int> preorderTraversal(TreeNode* root) {
 2         vector<int>vec;
 3         TreeNode* p = root;
 4         stack<TreeNode*>st;
 5         while(p!=nullptr || !st.empty())
 6         {
 7           while(p!=nullptr)
 8           {
 9             st.push(p);
10             vec.push_back(p->val);
11             p=p->left;
12           }
13           if(!st.empty())
14           {
15             p = st.top();
16             st.pop();
17             p = p->right;
18           }
19         }
20       return vec;
21     }

可以很明显看出先序与中序遍历几乎一样，但是实际上前者是在指针迭代时访问结点值，后者是在栈顶访问结点值。

具体实现可以参考这篇文章：https://www.jianshu.com/p/49c8cfd07410，当然我的思(dai)路(ma)也是从这里获(chao)取(xi)的(

[算法]二叉树的非递归遍历算法

推荐阅读