二叉树的中序遍历

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        vector<int> ret;
        display(root, ret);
        return ret;
    }
    //递归写法
    void display(TreeNode* root,vector<int>& ret)
    {
        if (root == NULL)
            return;
        display(root->left, ret);
        ret.push_back(root->val);
        display(root->right, ret);
    }
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root)
    {
        stack<pair<TreeNode*, string>> st;
        vector<int> ret;
        if (root == NULL)
            return ret;
        st.push({ root,"white" });
       //或者这样写： st.push((make_pair(root, "white")));
        while (!st.empty())
        {
            pair < TreeNode*, string > p= st.top();
            st.pop();
            if (p.first == NULL)
                continue;
            if (p.second == "white")
            {
                p.second = "grey";
                st.push({ p.first->right,"white" });
                st.push(p);
                st.push({ p.first->left,"white" });
            }
            else
                ret.push_back(p.first->val);
        }
        return ret;
    }
};

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