Easy

题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小绝对差 。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

  • 树中节点的数目范围是 [2, 10^4]
  • 0 <= Node.val <= 10^5

**注意：**本题与 783 题相同：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/

解题思路

这道题利用二叉搜索树的性质，可以用多种方法解决：

方法一：中序遍历（推荐） 二叉搜索树的中序遍历结果是有序的。我们可以在中序遍历过程中，记录前一个节点的值，然后计算当前节点与前一个节点的差值，维护最小差值即可。

方法二：收集所有值后排序 先遍历整棵树收集所有节点值，然后排序，再遍历相邻元素找最小差值。但这种方法没有充分利用BST的性质。

方法三：递归查找 对每个节点，找到其前驱和后继节点，计算差值。但这种方法时间复杂度较高。

中序遍历方法最优，时间复杂度O(n)，空间复杂度O(h)，其中h是树的高度。我们只需要一次遍历就能得到答案，充分利用了BST中序遍历有序的特点。

代码实现

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        int minDiff = INT_MAX;
        TreeNode* prev = nullptr;
        inorder(root, prev, minDiff);
        return minDiff;
    }
    
private:
    void inorder(TreeNode* node, TreeNode*& prev, int& minDiff) {
        if (!node) return;
        
        inorder(node->left, prev, minDiff);
        
        if (prev) {
            minDiff = min(minDiff, node->val - prev->val);
        }
        prev = node;
        
        inorder(node->right, prev, minDiff);
    }
};

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.min_diff = float('inf')
        self.prev = None
        
        def inorder(node):
            if not node:
                return
            
            inorder(node.left)
            
            if self.prev is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev)
            self.prev = node.val
            
            inorder(node.right)
        
        inorder(root)
        return self.min_diff

public class Solution {
    private int minDiff = int.MaxValue;
    private TreeNode prev = null;
    
    public int GetMinimumDifference(TreeNode root) {
        Inorder(root);
        return minDiff;
    }
    
    private void Inorder(TreeNode node) {
        if (node == null) return;
        
        Inorder(node.left);
        
        if (prev != null) {
            minDiff = Math.Min(minDiff, node.val - prev.val);
        }
        prev = node;
        
        Inorder(node.right);
    }
}

var getMinimumDifference = function(root) {
    let minDiff = Infinity;
    let prev = null;
    
    function inorder(node) {
        if (!node) return;
        
        inorder(node.left);
        
        if (prev !== null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;
        
        inorder(node.right);
    }
    
    inorder(root);
    return minDiff;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型中序遍历解法
时间复杂度O(n)
空间复杂度O(h)

其中 n 是树中节点的数量，h 是树的高度。空间复杂度主要来自递归调用栈的深度。

相关题目