This action will force synchronization from 程序员充电站/LeetCode-Py, which will overwrite any changes that you have made since you forked the repository, and can not be recovered!!!
Synchronous operation will process in the background and will refresh the page when finishing processing. Please be patient.
二叉搜索树(Binary Search Tree):也叫做二叉查找树、有序二叉树或者排序二叉树。是指一棵空树或者具有下列性质的二叉树:
- 如果任意节点的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。
- 如果任意节点的右子树不为空,则右子树上所有节点的值均大于它的根节点的值。
- 任意节点的左子树、右子树均为二叉搜索树。
如图所示,这 $3$ 棵树都是二叉搜索树。
二叉树具有一个特性,即:左子树的节点值 < 根节点值 < 右子树的节点值。
根据这个特性,如果我们以中序遍历的方式遍历整个二叉搜索树时,会得到一个递增序列。例如,一棵二叉搜索树的中序遍历序列如下图所示。
二叉搜索树的查找:在二叉搜索树中查找值为 $val$ 的节点。
按照二叉搜索树的定义,在进行元素查找时,我们只需要根据情况判断需要往左还是往右走。这样,每次根据情况判断都会缩小查找范围,从而提高查找效率。二叉树的查找步骤如下:
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
if val == root.val:
return root
elif val < root.val:
return self.searchBST(root.left, val)
else:
return self.searchBST(root.right, val)
二叉搜索树的插入:在二叉搜索树中插入一个值为 $val$ 的节点(假设当前二叉搜索树中不存在值为 $val$ 的节点)。
二叉搜索树的插入操作与二叉树的查找操作过程类似,具体步骤如下:
注意:二叉搜索树不允许存在重复节点,否则将违反其定义。因此,如果带插入节点在树中已存在,则不执行插入操作,直接返回。
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 root == None:
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
二叉搜索树的创建:根据数组序列中的元素值,建立一棵二叉搜索树。
二叉搜索树的创建操作是从空树开始,按照给定数组元素的值,依次进行二叉搜索树的插入操作,最终得到一棵二叉搜索树。具体算法步骤如下:
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 root == None:
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
def buildBST(self, nums) -> TreeNode:
root = TreeNode(val)
for num in nums:
self.insertIntoBST(root, num)
return root
二叉搜索树的删除:在二叉搜索树中删除值为 $val$ 的节点。
在二叉搜索树中删除元素,首先要找到待删除节点,然后执行删除操作。根据待删除节点所在位置的不同,可以分为 $3$ 种情况:
二叉搜索树的删除算法步骤如下:
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: TreeNode, val: int) -> TreeNode:
if not root:
return root
if root.val > val:
root.left = self.deleteNode(root.left, val)
return root
elif root.val < val:
root.right = self.deleteNode(root.right, val)
return root
else:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
curr = root.right
while curr.left:
curr = curr.left
curr.left = root.left
return root.right
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。