给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。递推写法

根据递归思想，先处理左子节点，然后输出，最后处理右子节点

在while(!q.empty())中左子节点直接入栈即可，最后处理右子节点的过程我们可以看成处理右子树，模仿递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> ans;
        stack<TreeNode *> q;
        TreeNode *cur = root;
        while (cur != nullptr || !q.empty()) {
            while (cur != nullptr) {
                q.push(cur);
                cur = cur->left;
            }
            cur = q.top();
            q.pop();
            ans.push_back(cur->val);
            cur = cur->right;
        }
        return ans;
    }
};