⭐️⭐️
1
题目描述
今天刷的是LeetCode的530题:给定一个节点值均为非负的二叉搜索树,求任意两节点差的绝对值的最小值。
2
知识点
知识点一:二叉搜索树
二叉搜索树同时满足以下几个条件:
并且,它的左、右子树也分别为二叉搜索树。
知识点二:python中的self理解
python中,用class来定义一个类,类中包含属性和调用方法,当创建一个该类的实例,这个实例也就拥有这个类的属性和调用方法。这里要注意以下几点:
结合题目中定义二叉树类的代码进行详细了解:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
类TreeNode是表示二叉树的类,这个类中有一个__init__调用方法,第一个参数是self,方法中的意思就是针对该类的实例,设置val为x,left为None,right为None,其中val、left、right是类的属性。
3
题解
思路:中序遍历
中序遍历指先访问左子树,再访问根节点,最后访问右子树。根据二叉搜索树的特点,经过中序遍历后,得到一个递增的列表,并且根据题目要求,想要得到差的绝对值的最小值,则一定是从两个相邻的值相减得到的,因此对递增列表相邻值求差,就可得到最后结果。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def getMinimumDifference(self, root: TreeNode):
#中序遍历
nodeorder = []
def inorder(root):#这里不是类的方法,只是对一个参数通过函数进行计算
if root.left is not None:
inorder(root.left)
nodeorder.append(root.val)
if root.right is not None:
inorder(root.right)
inorder(root)
#求相邻两个数的差值
for i in range(0,len(nodeorder)-1):
nodeorder[i] = nodeorder[i+1]-nodeorder[i]
return min(nodeorder[0:-1])