【代码随想录day20】二叉搜索树的最小绝对差-Toy模板网

这篇具有很好参考价值的文章主要介绍了【代码随想录day20】二叉搜索树的最小绝对差。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

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

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

【代码随想录day20】二叉搜索树的最小绝对差,代码随想录,LeetCode,数据结构,python,算法,leetcode

思路

最简单的一个思路是使用中序遍历，从二叉排序树中得到有序序列，存储到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_

当然也可以在中序遍历的过程中同时继续差值的最小值。文章来源地址https://www.toymoban.com/news/detail-607011.html

# 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

到了这里，关于【代码随想录day20】二叉搜索树的最小绝对差的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！