题解 | #二叉搜索树与双向链表#

//中序遍历 + 非递归 
class Solution {
public:
    TreeNode* Convert(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode *last_visit=nullptr, *ans=nullptr;
        while(!st.empty() || root)
        {
            while(root)
            {
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            if(last_visit == nullptr) 
            {
                ans = root;
            }
            else
            {
                root->left = last_visit;
                last_visit->right = root;
            }
            last_visit = root;
            root = root->right;
        }
        return ans;
    }
};

//中序遍历 + 递归(全局变量)
class Solution {
public:
    TreeNode* Convert(TreeNode* root) {
        if(!root) return nullptr;
        Convert(root->left);
        if(last_visit == nullptr)
        {
            ans = root;
        }
        else
        {
            root->left = last_visit;
            last_visit->right = root;
        }
        last_visit = root;
        Convert(root->right);
        return ans;
    }
private:
    TreeNode *ans=nullptr, *last_visit=nullptr;
};