题解 | #牛群最小体重差#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察了二叉搜索树的性质以及遍历，需要在二叉搜索树中找到相邻节点之间的最小差值。

题目解答方法的文字分析

对于二叉搜索树（BST），中序遍历可以得到一个升序序列。而在升序序列中，相邻两个节点之间的差值是最小的。因此，我们可以对树进行中序遍历，同时记录前一个节点的值，然后计算相邻节点值之间的差值，取最小值。

举个例子来帮助理解：

假设有以下二叉搜索树：

     4
    / \
   2   5
  / \
 1   3

中序遍历得到升序序列为：1, 2, 3, 4, 5。其中，相邻节点之间的最小差值为 1。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int minDiff = INT_MAX; // 初始化最小差值为最大整数
        
        TreeNode* prevNode = nullptr; // 用于记录前一个节点的指针
        inOrderTraversal(root, prevNode, minDiff); // 中序遍历
        
        return minDiff;
    }
    
    void inOrderTraversal(TreeNode* node, TreeNode*& prevNode, int& minDiff) {
        if (!node) {
            return;
        }
        
        inOrderTraversal(node->left, prevNode, minDiff); // 递归遍历左子树
        
        if (prevNode) {
            minDiff = min(minDiff, node->val - prevNode->val); // 计算相邻节点值之间的差值
        }
        prevNode = node; // 更新前一个节点
        
        inOrderTraversal(node->right, prevNode, minDiff); // 递归遍历右子树
    }
};

在这段代码中，我们通过中序遍历二叉搜索树，同时记录前一个节点的值，然后计算相邻节点值之间的差值，取最小值。在中序遍历的过程中，我们不断更新 prevNode，然后与当前节点的值进行计算。最终，返回最小差值作为结果。

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！