leetcode530：二叉搜索树的最小绝对值差

步骤1：问题定义与分析

• 输入：一个二叉搜索树的根节点
• 输出：树中任意两不同节点值之间的最小差值
• 限制条件：
  • 节点数量范围：[2, 10^4]
  • 节点值范围：[0, 10^5]
  • 差值必须为正数
• 关键特性：这是一个二叉搜索树(BST)，具有以下性质：
  • 左子树所有节点值小于根节点
  • 右子树所有节点值大于根节点
  • 中序遍历会得到一个有序序列

步骤2：解决方案分析

1. 方案一：暴力法

   • 获取所有节点值，两两比较
   • 时间复杂度：O(n^2)
   • 空间复杂度：O(n)
   • 不推荐，效率低

2. 方案二：利用BST特性（最优解）

   • 中序遍历BST得到有序序列
   • 相邻节点差值最小即为答案
   • 时间复杂度：O(n)
   • 空间复杂度：O(1)
   • 推荐使用，充分利用BST特性

步骤3：代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int minDiff = INT_MAX;  // 存储最小差值
    int prevVal = -1;       // 存储前一个节点的值
    
    // 中序遍历函数
    void inorderTraversal(TreeNode* root) {
        if (!root) return;
        
        // 遍历左子树
        inorderTraversal(root->left);
        
        // 处理当前节点
        if (prevVal != -1) {
            // 计算当前节点与前一个节点的差值
            minDiff = min(minDiff, root->val - prevVal);
        }
        prevVal = root->val;  // 更新前一个节点的值
        
        // 遍历右子树
        inorderTraversal(root->right);
    }
    
public:
    int getMinimumDifference(TreeNode* root) {
        inorderTraversal(root);
        return minDiff;
    }
};

步骤4：解题启发

1. 数据结构特性的重要性：

   • BST的中序遍历特性直接简化了问题
   • 正确利用数据结构特性可以大幅降低算法复杂度

2. 状态记录的技巧：

   • 使用prevVal记录前一个节点值，避免了额外的存储空间
   • 体现了空间优化的重要性