【代码随想录day20】二叉搜索树的最小绝对差_python二叉搜索树的最小绝对差-CSDN博客

本文链接：https://blog.csdn.net/doubleguy/article/details/131942832

文章讲述了如何解决找到二叉搜索树中任意两个不同节点值之间的最小差值问题。方法包括使用中序遍历得到有序序列后计算差值，或者在遍历过程中直接更新最小差值。两种方案都涉及到对二叉树的递归遍历。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

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

差值是一个正数，其数值等于两值之差的绝对值。

思路

最简单的一个思路是使用中序遍历，从二叉排序树中得到有序序列，存储到self.elem中，再线性扫描self.elem，计算相邻两个元素的差值，得到最小差值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.elem = []

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def solve(root):
            if not root:
                return 
            solve(root.left)
            self.elem.append(root.val)
            solve(root.right)
            
        solve(root)
        min_ = float('inf')
        for i in range(len(self.elem)-1):
            min_ = min_ if abs(self.elem[i]-self.elem[i+1])>=min_ else abs(self.elem[i]-self.elem[i+1])
        return min_

当然也可以在中序遍历的过程中同时继续差值的最小值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.pre = None
        self.res = float('inf')
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def solve(root):
            if not root:
                return
            solve(root.left)
            if not self.pre:
                self.pre = root
            else:
                self.res = self.res if abs(self.pre.val-root.val)>=self.res else abs(self.pre.val-root.val)
                self.pre = root
            solve(root.right)
        solve(root)
        return self.res