1. Morris遍历

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX;
        TreeNode* prev = nullptr;
        while(root) {
            if(root->left) {
                auto t = root->left;
                while(t->right && t->right != root) t = t->right;
                if(t->right == nullptr) t->right = root, root = root->left;
                else {
                    ans = min(ans, root->val - t->val);
                    t->right = nullptr, prev = root, root = root->right;
                }
            } else {
                if(prev) ans = min(ans, root->val - prev->val);
                prev = root, root = root->right;
            }
        }
        return ans;
    }
};

2. 非递归中序遍历

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int ans = INT_MAX;
        stack<TreeNode*> stk;
        TreeNode* prev = nullptr;
        while(root || stk.size()) {
            if(root) {
                stk.push(root);
                root = root->left;
            } else {
                root = stk.top(); stk.pop();
                if(prev) ans = min(ans, root->val - prev->val);
                prev = root;
                root = root->right;
            }
        }
        return ans;
    }
};

3. 递归中序遍历

class Solution {
public:
    int ans;
    int minDiffInBST(TreeNode* root) {
        this->ans = INT_MAX;
        int pre = -1;
        dfs(root, pre);
        return ans;
    }

    void dfs(TreeNode* root, int& pre) {
        if(!root) return;
        dfs(root->left, pre);
        if(pre != -1) ans = min(ans, root->val - pre);
        pre = root->val;
        dfs(root->right, pre); 
    }
};