LeetCode 530. Minimum Absolute Difference in BST 题解

张开发
• 2026/4/5 20:13:08 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode 530. Minimum Absolute Difference in BST 题解
LeetCode 530. Minimum Absolute Difference in BST 题解题目描述给你一个二叉搜索树的根节点root返回树中任意两不同节点值之间的最小绝对差。示例 1输入root [4,2,6,1,3] 输出1示例 2输入root [1,0,48,null,null,12,49] 输出1解题思路方法中序遍历思路二叉搜索树的中序遍历结果是一个递增的序列因此我们可以对二叉树进行中序遍历然后计算相邻元素之间的绝对差找到最小的那个复杂度分析时间复杂度O(n)其中 n 是二叉搜索树的节点个数。需要遍历二叉树一次。空间复杂度O(n)需要使用栈来进行中序遍历以及存储遍历结果。代码实现方法中序遍历# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) - int: # 中序遍历二叉树 def inorder(node): if not node: return [] return inorder(node.left) [node.val] inorder(node.right) # 计算相邻元素之间的绝对差找到最小的那个 inorder_result inorder(root) min_diff float(inf) for i in range(1, len(inorder_result)): min_diff min(min_diff, inorder_result[i] - inorder_result[i-1]) return min_diff测试用例测试用例 1输入root [4,2,6,1,3]输出1测试用例 2输入root [1,0,48,null,null,12,49]输出1总结本题是二叉搜索树的经典问题主要考察对二叉搜索树性质的理解和应用。通过使用中序遍历我们可以高效地找到二叉搜索树中任意两不同节点值之间的最小绝对差。中序遍历的核心思想是二叉搜索树的中序遍历结果是一个递增的序列因此我们可以计算相邻元素之间的绝对差找到最小的那个。这种方法不仅适用于二叉搜索树的最小绝对差问题还可以应用于许多其他需要遍历二叉搜索树并计算节点值之间差异的场景。掌握中序遍历的思想对于解决这类问题非常重要。

更多文章