题解 | #二叉搜索树最小差值#递归遍历

方法一（更容易理解）

• 先中序遍历取出二叉搜索树的升序数组（二叉搜索树都是左小右大）
• 然后遍历相减，比大小

c++实现

class Solution {
public:
    vector<int> t;
    void mid(TreeNode* root){
        if(!root) return ;
        mid(root->left);
        t.push_back(root->val);
        mid(root->right);
    }
    
    int minDifference(TreeNode* root) {
        // write code here
        mid(root); //中序遍历，将二叉搜索树升序取出来
        if(t.size() < 2) return -1;
        int v=t[1]-t[0];
        for(int i=1; i<t.size()-1; i++){
            if(t[i+1]-t[i] < v){
                v = t[i+1]-t[i];
            }
        }
        return v;
    }
};

方法二（效率更高）

其实二叉树一次遍历就可以解决这个问题：

• 用当前节点减去左子节点(root - root->left)，取min值
• 用当前节点的右子节点减去当前节点（root->right - root），取min值
• 递归左节点、右节点

c++实现

class Solution {
public:
    void func(TreeNode* root, int &res){
        if(!root) return;
        if(root->left) res = min(res, root->val - root->left->val);
        if(root->right) res = min(res, root->right->val - root->val);
        func(root->left, res);
        func(root->right, res);
    }
    
    int minDifference(TreeNode* root) {
        int res = INT_MAX;
        func(root, res);
        return res;
    }
};