二叉树二叉搜索BST树验证二叉搜索树中的搜索二叉搜索树的最小绝对差
目录
【二叉树】二叉搜索（BST）树验证、二叉搜索树中的搜索、二叉搜索树的最小绝对差
目录
#学习记录#
今天我们来看看二叉搜索树的问题，
对应力扣：
- 二叉搜索树中的搜索：
2.验证二叉搜索树：
3.二叉搜索树的最小绝对差：
什么是二叉搜索树：
🌟 二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它有一些独特的特性，非常适合用来存储数据并快速地进行查找、插入和删除操作。
二叉搜索树的基本概念：
结构特点 ：每个节点有最多两个子节点，通常被称为“左子节点”和“右子节点”。
排序规则 ：
- 每个节点的左子树只包含小于该节点的值。
- 每个节点的右子树只包含大于该节点的值。
- 没有两个节点拥有相同的值。
查找效率 ：由于二叉搜索树的排序特性，查找效率通常比较高。在最理想的情况下（树是平衡的），查找操作的时间复杂度为O(log n)，其中n是树中节点的数量。
插入和删除 ：插入和删除操作需要维护二叉搜索树的排序规则，通常也是O(log n)的时间复杂度（在树平衡的情况下）。
举个例子：
5
/ \
3 8
/ \ \
1 4 91.二叉搜索树中的搜索
题目描述：
搜索算法步骤：
- 开始于根节点 ：搜索操作从树的根节点开始。
- 比较搜索值 ：将搜索值与当前节点的值进行比较。
- 决定方向
：
- 如果搜索值等于当前节点的值，搜索成功。
- 如果搜索值小于当前节点的值，移动到左子节点继续搜索。
- 如果搜索值大于当前节点的值，移动到右子节点继续搜索。
- 递归或迭代 ：重复上述过程，直到找到值或达到叶子节点（没有子节点的节点）。
效率 ：
- 在平衡的BST中，搜索操作的时间复杂度为O(log n)，其中n是树中节点的数量。
- 在最坏的情况下（树完全不平衡），时间复杂度可能退化为O(n)。
# 递归法
def searchBST(root, val):
if root is None or val == root.val:
return root
if val < root.val:
return searchBST(root.left, val)
else:
return searchBST(root.right, val)除了递归法外，我们还可以使用迭代法，更好理解：
def searchBST(self, root, val):
cur = root
while cur is not None:
if cur.val == val:
break
if val > cur.val:
cur = cur.right
continue
if val < cur.val:
cur = cur.left
continue
return cur2.验证二叉搜索树：
题目描述：
解题思路及方法
根据二叉树的特性，我们可以发现，当二叉树中序遍历（左中右）时，结果是从小到大的列表。那么我们最简单的方式就是将其保存在列表中，然后对列表进行判断。
我们先来回顾一下 二叉树的中序遍历 ：
# 递归
result = []
def inorder(root):
if not root:
return []
inorder(root.left) # 左
result.append(root.val) # 中
inorder(root.right) # 右
# 力扣中写在方法内记得在方法前加上self使用递归方法非常简洁
我们再回顾一下 迭代法 ，这里需要调用栈来辅助我们进行迭代
# 二叉树的中序遍历（迭代）
def inorder(root):
stack = []
result = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
result.append(cur.val)
cur = cur.right
result result复习过中序遍历后我们来撰写本题：
先来简单的，如果 先求得中序列表再判断 ，代码为：
class Solution:
def inorder(self, root):
# 中序遍历
if not root:
return []
return self.inorder(root.left) + [root.val] + self.inorder(root.right)
# 这里对代码进行了精简
def isSorted(self, lst):
# 判断一个列表是否递增
for i in range(1, len(lst)):
if lst[i] <= lst[i - 1]:
return False
return True
def isValidBST(self, root):
# 判断是否是二叉搜索树
return self.isSorted(self.inorder(root))同时我们还可以 在遍历的过程中进行判断 ，我们只需要比较前一个元素是够比当前元素大即可，这里我们需要提前设定一个pre
class Solution:
def __init__(self):
self.prev = None
def inorder(self, root):
# 中序遍历
if not root:
return True
if not self.inorder(root.left):
return False
if self.prev and self.prev.val >= root.val:
return False
self.prev = root
return self.inorder(root.right)
def isValidBST(self, root):
# 判断是否是二叉搜索树
return self.inorder(root)3.二叉搜索树的最小绝对差
题目描述：
算法步骤 :
- 中序遍历 ：对BST进行中序遍历，获得一个按升序排列的节点值列表。
- 计算相邻差值 ：遍历这个列表，计算相邻元素之间的差值。
- 找出最小差值 ：记录并更新这些差值中的最小值。
为什么使用中序遍历 ： 中序遍历BST会得到一个按升序排列的值序列，最小差值一定在相邻的两个值之间产生。这使得算法非常高效。
代码示例（Python） :
class Solution:
def getMinimumDifference(self, root):
self.prev = None
self.min_diff = float('inf')
def inorder(node):
if not node:
return
inorder(node.left)
if self.prev is not None:
self.min_diff = min(self.min_diff, node.val - self.prev.val)
self.prev = node
inorder(node.right)
inorder(root)
return self.min_diff以上，学习在于坚持和总结，共勉
