二叉树的中序遍历（非递归）

总结二叉树的非递归实现：

1. 先序遍历——采用栈和一个辅助指针，不断访问节点，并将左侧节点入栈，然后出栈访问右侧节点
2. 中序遍历——采用栈和一个辅助指针，将左侧节点入栈，然后访问中间节点，最后再入栈右侧节点
3. 后序遍历——最难的一个，采用栈和两个辅助指针，其中有一个辅助指针记录上一个访问的节点，如果是当前节点的右子节点，则访问当前节点

中序遍历如下：

//
// Created by jt on 2020/8/23.
//
#include <vector>
#include <stack>
using namespace std;


class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector
     */
    vector<int> inorderTraversal(TreeNode *root) {
        // write code here
        vector<int> res;
        if (!root) return res;
        stack<TreeNode *> st; TreeNode *p = root;
        while (!st.empty() || p) {
            while (p) {
                st.push(p);
                p = p->left;
            }
            if (!st.empty()) {
                TreeNode *node = st.top();
                st.pop();
                res.push_back(node->val);
                p = node->right;
            }
        }
        return res;
    }
};