题解 | #二叉树的中序遍历# 使用栈

递归写法比较简单，直接按遍历的顺序在合适的位置将当前节点的数值插入即可。比较麻烦的是不使用系统给我维护的堆栈，我自己创建堆栈来实现整个过程。

• 1. 首先中序遍历，最先要遍历的是左子树的节点，然后才是根节点，再来是右子树节点
• 2. 我们先思考下堆栈的特点，是先进后出，先入栈的最后出来，最后如战斗的最先出来
• 3. 再回来看我们的需求，我们要求最先拿到的是左子树的节点，结合堆栈的特点，我们就可以这样操作，首先无脑搜索左子树，一直搜索到空节点为止，同时整个过程中将所有的节点全部入栈， 最后我们发现，此时栈顶的元素就是最左边的元素，ok，初步的小目标实现
• 4. 此时我们发现，当我们弹出来一个数的时候，假如它又有右节点，右节点上又又挂了左子树怎么办？套路一样，我们首先判断该节点是否又右子树，有的话，先将右子数入栈，然后再次无脑探索这个右子树的左子树，一直搜到搜不动为止（遇到空节点了）
• 5. 循环往复，即可实现中序遍历
• 6. 说的可能有点绕，直接看代码就清晰了（Talk is cheap. Show me the code!）

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == nullptr) return res;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(cur){
            st.push(cur);
            cur = cur->left;
        }
        while(!st.empty()){
            cur = st.top();
            st.pop();
            res.push_back(cur->val);
            if(cur->right){
                cur = cur->right;
                while(cur){
                    st.push(cur);
                    cur = cur->left;
                }
            }
        }     
        return res;
    }
};