Leetcode 530. 二叉搜索树的最小绝对差

Table of Contents

题解
#

方法一：中序遍历 + 遍历差值
#

思路
#

二叉搜索树的中序遍历是一个递增的序列，所以我们可以通过中序遍历来获取树中任意两个不同节点值之间的最小差值。

具体做法是，先进行中序遍历，将遍历的结果保存在一个数组中。然后，遍历数组，计算相邻两个元素之间的差值，找到最小的差值。

复杂度分析
#

时间复杂度：遍历一次二叉搜索树需要 O(n) 的时间，其中 n 是树中的节点数。遍历结果数组需要 O(n) 的时间，计算差值需要 O(n) 的时间。所以总时间复杂度为 O(n)。
空间复杂度：中序遍历结果的数组大小为 n，所以空间复杂度为 O(n)。

实现
#

C++

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        vector<int> nums;
        inorderTraversal(root, nums);
        
        int minDiff = INT_MAX;
        for (int i = 1; i < nums.size(); i++) {
            minDiff = min(minDiff, nums[i] - nums[i-1]);
        }
        
        return minDiff;
    }
    
private:
    void inorderTraversal(TreeNode* node, vector<int>& nums) {
        if (node == nullptr) {
            return;
        }
        
        inorderTraversal(node->left, nums);
        nums.emplace_back(node->val);
        inorderTraversal(node->right, nums);
    }
};