[数据结构与算法]二叉数中序遍历的非递归算法

学校老师教的，思路贼清晰，大家可以借鉴一下。

每遇到一个结点就将它压栈，然后去遍历其左子树，左子树遍历完之后，从栈顶取出这个结点并访问，然后通过给的右子树的链接地址取访问它的右子树。

当前指针为空有两种情况：1.根的左子树已经找完，2.没有右子树。

总体来说就是:将遇到的每个结点压栈，遍历每个结点的左子树，如果pointer即当前指针为空(此根的左子树找完了)(又或者说栈顶结点没有左孩子)，那么就弹出栈顶结点，访问将其val存到数组内，
￥(此为标记)然后找弹出的结点的右孩子，然后继续向下找左子树，直到某个结点的左孩子没了，且右孩子也没了，那么此时pointer为空就会走while循环中的else，去弹栈，pointer指向最后一个结点的上一个结点，(上一个结点的左孩子已经存到了栈内)去判断此时pointer指向的结点是否有右孩子，
如果有则重复￥处的操作，如果没有，那么就可以继续一直走else,不断的弹栈，将val值不断的存入数组内，直到当pointer走到根节点，此时栈为空，但是pointer不为空，它指向根节点，然后重复￥处的操作。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //调用STL中的栈
#include<stack>
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
    using std:: stack;
    stack<TreeNode*> astack;
    TreeNode* pointer = root;
    vector<int> res;
    while(!astack.empty()||pointer)
    {
        if(pointer)
        {
            astack.push(pointer);
            pointer = pointer->left;
        }
        else
        {
            pointer = astack.top();
            astack.pop();//千万要记得出栈。
            res.push_back(pointer->val);
            pointer = pointer->right;
        }
    }
    return res;
    }
};

力扣的中序遍历