描述
给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
在线评测地址:领扣题库官网
样例1 输入: root = {4,2,6,1,3} 输出: 1 注意,root是树结点对象(TreeNode object),而不是数组。 给定的树 [4,2,6,1,3,null,null] 可表示为下图: / \ 1 3 最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
样例2 输入: root = {2,1} 输出: 1 注意,root是树结点对象(TreeNode object),而不是数组。 给定的树 {2,1} 可表示为下图: 最小的差值是 1, 它是节点1和节点2的差值。
解题思路
二叉搜索树,根据树的性质,知道root的右子树都是大于它的,左子树都是小于它的。
那么如果做中序遍历,标准的做法是得到一个递增的序列。
我们就先遍历左根,节点,右根,这样就会得到一个递增的序列。
然后对这个序列相邻相减,取最小值即可。 实现时,可以优化掉这个序列。
在遍历时记录上一个访问的节点值,和当前节点相减,记录下最小值即可。
源代码
""" Definition of TreeNode: class TreeNode: def __init__(self, val): self.val = val self.left, self.right = None, None class Solution: @param root: a Binary Search Tree (BST) with the root node @return: the minimum difference pre = -float('inf') res = float('inf') def minDiffInBST(self, root): # Write your code here. if root.left: self.minDiffInBST(root.left) self.res = min(self.res, root.val - self.pre) self.pre = root.val if root.right: self.minDiffInBST(root.right) return self.res
更多题解参考:九章官网solution
边缘计算的下一步是什么,它将如何影响您的战略?专家权衡边缘趋势并讨论工作负载...
基本介绍 过去十年来,OAuth2授权协议备受争议,您可能已经听说过很多return_uri...
一、数据结构的存储方式 数据结构的存储方式只有两种:数组(顺序存储)和链表(链...
无论是专业的数据分析师还是销售、人力等基本的业务岗位,在汇报时总是免不了要...
阿里巴巴程序员的速度 论技术水平没得说 论干饭能力 也是惊人 阿里人1年吃掉495...
背景介绍 ? ? ? ? 为了摸底项目的性能,需要进行性能测试。经过一番调研之后,决...
问题描述 Linux裸金属服务器的静态主机名来源于创建裸金属服务器时,通过控制台...
根据裸金属服务器的网络设置,以及您本地设备的操作系统,您可以选择合适的方法...
云岫资本企服组 2021 年 3 月 【前言】随着业务上云、生态协作、多云混合等场景...
TOP云 1月11日讯,纵观上周西数平台的交易纪录,在一口价前三和竞拍价前三的榜单...