算法练习-二叉搜索树的最小绝对差（思路+流程图+代码）

难度参考

        难度：中等

        分类：二叉树

        难度与分类由我所参与的培训课程提供，但需要注意的是，难度与分类仅供参考。且所在课程未提供测试平台，故实现代码主要为自行测试的那种，以下内容均为个人笔记，旨在督促自己认真学习。

题目

        给你一个二叉搜索树的根节点root，返回树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。
        示例1:
        输入：root=[4,2,6,1,3]
        输出：1

        示例2:
        输入：root=[1,0,48,null,null,12,49]
        输出：1

        提示：
        树中节点的数目范围是 [2,10(4)]
        0<=Node.Va1<=10(5)

思路

        要在二叉搜索树中找到任意两个节点差值的最小值，我们可以利用二叉搜索树的性质，即中序遍历得到的值是递增的。在中序遍历过程中，我们只需保持跟踪前一个节点的值，并与当前节点的值求差的绝对值，进而不断更新最小差值即可。

        具体步骤：

1. 初始化一个变量minDiff作为最小差值，并将其设置为一个非常大的数（例如INT_MAX）。
2. 初始化一个变量prev用于存储上一个访问过的节点，开始时为nullptr。
3. 对树进行中序遍历，按照左节点、根节点、右节点的顺序。
4. 在访问每个节点时，如果前一节点prev不是nullptr（也就是说这不是访问的第一个节点），那么计算当前节点和前一节点的差值的绝对值，更新minDiff为当前差值与minDiff之中的较小值。
5. 将当前节点设置为新的prev，然后继续遍历。
6. 中序遍历完成后，minDiff中存储的就是任意两个节点差值的最小值。

示例

        二叉搜索树（Binary Search Tree），也称为二叉排序树或二叉查找树，它是一种特殊的二叉树，具有以下性质：

• 如果二叉搜索树不是空树，则它的左子树中的所有结点的值都小于它的根结点的值。
• 如果二叉搜索树不是空树，则它的右子树中的所有结点的值都大于它的根结点的值。
• 每一层（除了最底层）的结点数量不超过最大结点数的半数。

        此外，二叉搜索树的左子树和右子树自身也是二叉搜索树。这种结构使得二叉搜索树非常适合用于快速检索，即二分搜索算法。

        假设我们有如下这棵二叉搜索树（BST）：

     4
   /   \
  2     6
 / \
1   3

        我们要找到BST中任意两个不同节点之间的最小差值。

1. 对树执行中序遍历（左->右->根），访问顺序将会是 1 -> 2 -> 3 -> 4 -> 6，因为二叉搜索树中序遍历的结果是升序排列的。

2. 开始时，minDiff初始化为INT_MAX（一个非常大的数），prevNode初始化为nullptr。

3. 访问节点 1:

   • prevNode是nullptr，所以我们不更新minDiff。
   • 将prevNode设置为指向当前节点（值为 1 的节点）。

4. 访问节点 2:

   • 现在prevNode不是nullptr，计算差值abs(2 - 1)得到 1。
   • 更新minDiff为min(INT_MAX, 1)，因此minDiff现在是 1。
   • 更新prevNode为当前节点（值为 2 的节点）。

5. 访问节点 3:

   • 计算差值abs(3 - 2)得到 1。
   • 更新minDiff为min(1, 1)，因此minDiff保持为 1。
   • 更新prevNode为当前节点（值为 3 的节点）。

6. 访问节点 4:

   • 计算差值abs(4 - 3)得到 1。
   • 更新minDiff为min(1, 1)，因此minDiff保持为 1。
   • 更新prevNode为当前节点（值为 4 的节点）。

7. 访问节点 6:

   • 计算差值abs(6 - 4)得到 2。
   • 更新minDiff为min(1, 2)，因此minDiff保持为 1。
   • 更新prevNode为当前节点（值为 6 的节点）。

8. 中序遍历完成，所有节点都已经访问过，minDiff现在存储的是任意两个节点的最小差值，这个例子中为 1。

梳理

        在二叉搜索树（Binary Search Tree，BST）中，中序遍历可以按照顺序访问节点。所以，通过对BST执行中序遍历，我们可以得到一个升序排列的节点序列。

        利用中序遍历，我们可以通过在遍历的过程中计算相邻节点之间的差值来减少比较的次数。

        具体来说，我们用两个变量来追踪状态：

• prevNode：指向前一个访问的节点。
• minDiff：存储当前找到的最小差值。

        在遍历过程中，我们比较当前节点与前一个节点之间的差值，并将其与之前找到的最小差值进行比较和更新。

        由于中序遍历的性质，对于相邻的节点，它们之间的差值将是最小的。所以我们只需要在遍历过程中比较相邻节点的差值，并将其与当前的最小差值进行比较和更新。

        通过这种方法，我们可以在遍历完整个BST之后找到任意两个不同节点之间的最小差值，而不需要比较所有可能的差值。

代码

#include <iostream>  // 包含输入输出流的库
#include <cmath>  // 包含数学库
#include <climits>  // 包含整数类型的极限值宏

using namespace std;  // 使用std命名空间

struct TreeNode {  // 定义结构体TreeNode
    int val;  // 节点值
    TreeNode *left;  // 左子节点指针
    TreeNode *right;  // 右子节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}  // 构造函数
};

int minDiff = INT_MAX;  // 定义全局变量 minDiff，初始化为整数类型的最大值
TreeNode* prevNode = nullptr;  // 定义全局变量 prevNode，初始化为nullptr

void inorder(TreeNode* node) {  // 定义中序遍历函数 inorder
    if (!node) return;  // 如果节点为空，返回
    
    inorder(node->left);  // 递归调用：遍历左子树

    if (prevNode) {  // 如果 prevNode 不为空
        minDiff = min(minDiff, abs(node->val - prevNode->val));  // 计算当前节点值与前一个节点值的差的绝对值，并与 minDiff 进行比较和更新
    }
    prevNode = node;  // 更新 prevNode 为当前节点

    inorder(node->right);  // 递归调用：遍历右子树
}

int getMinimumDifference(TreeNode* root) {  // 定义函数 getMinimumDifference，参数为根节点
    inorder(root); // 进行中序遍历更新最小差值 minDiff
    return minDiff;  // 返回最小差值
}

// 主函数
int main(){
    TreeNode *root1 = new TreeNode(4);  // 创建二叉树，根节点值为4
    root1->left = new TreeNode(2);  // 设置左子节点的值为2
    root1->right = new TreeNode(6);  // 设置右子节点的值为6
    root1->left->left = new TreeNode(1);  // 设置左子节点的左子节点的值为1
    root1->left->right = new TreeNode(3);  // 设置左子节点的右子节点的值为3

    cout << "示例1: " << getMinimumDifference(root1) << endl; // 应该输出 1
    
    // 清理内存
    delete root1->left->left;
    delete root1->left->right;
    delete root1->left;
    delete root1->right;
    delete root1;
    minDiff = INT_MAX;  // 重置 minDiff 和 prevNode 以进行下一个测试
    prevNode = nullptr;

    TreeNode *root2 = new TreeNode(1);  // 创建二叉树，根节点值为1
    root2->left = new TreeNode(0);  // 设置左子节点的值为0
    root2->right = new TreeNode(48);  // 设置右子节点的值为48
    root2->right->left = new TreeNode(12);  // 设置右子节点的左子节点的值为12
    root2->right->right = new TreeNode(49);  // 设置右子节点的右子节点的值为49
    
    cout << "示例2: " << getMinimumDifference(root2) << endl; // 应该输出 1

    // 清理内存
    delete root2->left;
    delete root2->right->left;
    delete root2->right->right;
    delete root2->right;
    delete root2;
    
    return 0;  // 返回0表示成功
}

        时间复杂度：O(n)

        空间复杂度：O(n)

打卡