题目：

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

题意：

给定一个二叉树，返回它的中序 遍历。

思路：

经典题目了，递归版和非递归版，时间复杂度均为$O(n)$O(n)

代码：

递归版：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        inorder(root, ans);
        return ans;
    }
    
    void inorder(TreeNode *root, vector<int> &ans) {
        if(root == nullptr) {
            return;
        }

        inorder(root->left, ans);
        ans.emplace_back(root->val);
        inorder(root->right, ans);
    }
    
};

非递归版：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        while(root || !stk.empty()) {
            if(root) {
                stk.emplace(root);
                root = root->left;
            } else {
                root = stk.top(); stk.pop();
                ans.emplace_back(root->val);
                root = root->right;
            }
        }

        return ans;
    }
};