递归很简单，不说了。

非递归：用栈来模拟整个递归的过程，但是栈放一个 pair<TreeNode*, bool>，bool 为 false 表示当前这个节点并未向左延伸

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<pair<TreeNode*, bool>> stk;   // bool = false 表示向左扩展
        if(root) stk.push({root, false});
        while(!stk.empty()) {
            pair<TreeNode*, bool> &top = stk.top();
            if((!top.second && top.first -> left == nullptr) || top.second) {
                ans.emplace_back(top.first -> val);
                stk.pop();
                if (top.first -> right) stk.push({top.first -> right, false});
                continue;
            }
            if(!top.second) {
                top.second = true;
                stk.push({top.first -> left, false});
                continue;
            }
            if (top.first -> right) stk.push({top.first -> right, false});
        }
        return ans;
    }
};