二叉搜索樹相關題目總結（一） 力扣 Python

總結一下與二叉搜索樹有關的題目，解決思路都是二叉搜索樹的相關操作。

98. 驗證二叉搜索樹

解題思路：

驗證一顆樹是不是二叉搜索樹（BST）？

依據二叉搜索樹的性質寫出代碼，如下注釋。

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.check(root)
def check(self, root, min_val = float('-inf'), max_val = float('inf')) -> bool:
# 默認為True
if not root:
return True
#一旦當前節點比最小值小，或者比最大值大，就不是二叉搜索樹
if root.val <= min_val or root.val >= max_val:
return False
#分別檢查左子樹和右子樹
return self.check(root.left, min_val, root.val) and self.check(root.right, root.val, max_val)

700. 二叉搜索樹中的搜索

解題思路：
利用 BST 的特性，進行搜索。

如果當前節點小於目標值就去右子樹查找。

如果當前節點大於目標值就去左子樹查找。

# 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 searchBST(self, root: TreeNode, val: int) -> TreeNode:
if not root:
return None
#利用二叉搜索樹的性質，查找 val
if val < root.val:
return self.searchBST(root.left, val)
if val > root.val:
return self.searchBST(root.right, val)
return root

701. 二叉搜索樹中的插入操作

解題思路：

在二叉搜索樹查找的基礎上，修改相關代碼變差插入。

# 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 insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
#找到空位置插入新節點
if not root:
return TreeNode(val)
# 對遞歸調用的返回值進行接收
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
if val > root.val:
root.right = self.insertIntoBST(root.right, val)
return root

450. 刪除二叉搜索樹中的節點

解題思路：

BST 的刪除要比前面的三道題復雜一些。

主要是被刪除的節點在樹中有三種情況。

• 情況1，當前節點沒有子節點，直接刪除。
• 情況2，當前節點有一個左子節點或右子節點，刪除當前節點，並用存在的子節點接替當前子節點。
• 情況3，當前節點右兩個子節點，刪除當前節點，用左子節點中最大的節點的來接替，或用右子節點中最小的來接替。

# 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 deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if root.val > key:
root.left = self.deleteNode(root.left, key)
elif root.val < key:
root.right = self.deleteNode(root.right, key)
#找到節點值為 key
else:
#處理情況 1， 2
if not root.left:
return root.right
if not root.right:
return root.left
#處理情況3,這裡使用右子樹中最小的來接替
minNode = self.getMin(root.right)
# 刪除右子樹中最小的節點
root.right = self.deleteNode(root.right, minNode.val)
#替換節點
minNode.left, minNode.right = root.left, root.right
root = minNode
return root
def getMin(self, root):
#根據BST的性質，最左邊的就是最小的
while root.left:
root = root.left
return root