中序遍历非递归法

使用的是LeetCode评论中的颜色标记法

官方题解中介绍了三种方法来完成树的中序遍历，包括：

递归
借助栈的迭代方法
莫里斯遍历
在树的深度优先遍历中（包括前序、中序、后序遍历），递归方法最为直观易懂，但考虑到效率，我们通常不推荐使用递归。

栈迭代方法虽然提高了效率，但其嵌套循环却非常烧脑，不易理解，容易造成“一看就懂，一写就废”的窘况。而且对于不同的遍历顺序（前序、中序、后序），循环结构差异很大，更增加了记忆负担。

因此，我在这里介绍一种“颜色标记法”（瞎起的名字……），兼具栈迭代方法的高效，又像递归方法一样简洁易懂，更重要的是，这种方法对于前序、中序、后序遍历，能够写出完全一致的代码。

其核心思想如下：

使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。
使用这种方法实现的中序遍历如下：

作者：hzhu212
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

注意这里由于是压入栈中，左中右的中序遍历颠倒，变成右中左的顺序。

执行用时 :
0 ms
, 在所有 C++ 提交中击败了
100.00%
的用户
内存消耗 :
9.3 MB
, 在所有 C++ 提交中击败了
30.80%
的用户

stl stack top方法 push pop方法
以及make_pair方法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        //学习迭代算法中序遍历
        vector<int> res;
        if(!root)
            return res;
        stack<pair<TreeNode*,int>> mid;
        int white=0;
        int gray=1;
        pair<TreeNode*,int> firs(root,0);
        mid.push(firs);
        while(!mid.empty()){
            pair<TreeNode*,int> tmp=mid.top();
            mid.pop();
            if(tmp.second==0){//左中右
                                 
                if(tmp.first->right){
                    mid.push(make_pair(tmp.first->right,white));
                }
                 mid.push(make_pair(tmp.first,gray));
                if(tmp.first->left){
                    mid.push(make_pair(tmp.first->left,white));
                   
                }


            }else{
                res.push_back(tmp.first->val);
            }
            
        }
        return res;
        
        
    }
};