Easy

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

**注意：**本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同

解题思路

这道题要求找到二叉搜索树中任意两个不同节点值之间的最小差值。

**核心思路：**利用二叉搜索树的性质 - 中序遍历得到的序列是有序的。因此最小差值一定出现在中序遍历序列中相邻的两个节点之间。

解法一：中序遍历 + 数组存储

  • 先进行中序遍历，将所有节点值存储到数组中
  • 遍历数组，计算相邻元素的差值，找到最小值
  • 时间复杂度：O(n)，空间复杂度：O(n)

解法二：中序遍历 + 一次扫描（推荐）

  • 在中序遍历过程中，维护前一个访问的节点值
  • 每访问一个新节点时，计算与前一个节点的差值
  • 实时更新最小差值，无需额外存储空间
  • 时间复杂度：O(n)，空间复杂度：O(h)，其中h为树的高度

由于BST的特性，相邻节点在中序遍历中必然相邻，所以只需要比较相邻节点即可找到全局最小差值。

代码实现

class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int minDiff = INT_MAX;
        int prev = -1;
        
        function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (!node) return;
            
            inorder(node->left);
            
            if (prev != -1) {
                minDiff = min(minDiff, node->val - prev);
            }
            prev = node->val;
            
            inorder(node->right);
        };
        
        inorder(root);
        return minDiff;
    }
};

class Solution:
    def minDiffInBST(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 int prev = -1;
    
    public int MinDiffInBST(TreeNode root) {
        Inorder(root);
        return minDiff;
    }
    
    private void Inorder(TreeNode node) {
        if (node == null) return;
        
        Inorder(node.left);
        
        if (prev != -1) {
            minDiff = Math.Min(minDiff, node.val - prev);
        }
        prev = node.val;
        
        Inorder(node.right);
    }
}

var minDiffInBST = function(root) {
    let minDiff = Infinity;
    let prev = null;
    
    const 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(n)
空间复杂度O(h)O(n)

其中 n 是树中节点的个数，h 是树的高度。推荐使用中序遍历一次扫描的方法，空间效率更高。

相关题目