概述
二叉搜索树是二叉树的一种特殊形式。 二叉搜索树具有以下性质：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值。
二叉搜索树（BST）是二叉树的一种特殊表示形式，它满足如下特性：
每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
每个节点中的值必须小于（或等于）存储在其右子树中的任何值。
在二叉搜索树中实现搜索操作 - 介绍
二叉搜索树主要支持三个操作：搜索、插入和删除。 在本章中，我们将讨论如何在二叉搜索树中搜索特定的值。
根据BST的特性，对于每个节点：
如果目标值等于节点的值，则返回节点；
如果目标值小于节点的值，则继续在左子树中搜索；
如果目标值大于节点的值，则继续在右子树中搜索。
在二叉搜索树中实现插入操作 - 介绍
二叉搜索树中的另一个常见操作是插入一个新节点。有许多不同的方法去插入新节点，这篇文章中，我们只讨论一种使整体操作变化最小的经典方法。 它的主要思想是为目标节点找出合适的叶节点位置，然后将该节点作为叶节点插入。 因此，搜索将成为插入的起始。
与搜索操作类似，对于每个节点，我们将：
- 根据节点值与目标节点值的关系，搜索左子树或右子树；
- 重复步骤 1 直到到达外部节点；
- 根据节点的值与目标节点的值的关系，将新节点添加为其左侧或右侧的子节点。
举例:(来源力扣)
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]
插入一个数,需要考虑的是判断跟根节点的大小来判断插入哪一个子树,如果下面没有子树,则直接进行插入就可以了,如果有子树,就需要继续比较大小,知道到达叶子节点.
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){
return new TreeNode(val);
}
if(root.val>val){
root.left=insertIntoBST(root.left,val);
}else{
root.right=insertIntoBST(root.right,val);
}
return root;
}
}
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
TreeNode pos = root;
while (pos != null) {
if (val < pos.val) {
if (pos.left == null) {
pos.left = new TreeNode(val);
break;
} else {
pos = pos.left;
}
} else {
if (pos.right == null) {
pos.right = new TreeNode(val);
break;
} else {
pos = pos.right;
}
}
}
return root;
}
}
在二叉搜索树中实现删除操作 - 介绍
删除要比我们前面提到过的两种操作复杂许多。有许多不同的删除节点的方法，这篇文章中，我们只讨论一种使整体操作变化最小的方法。我们的方案是用一个合适的子节点来替换要删除的目标节点。根据其子节点的个数，我们需考虑以下三种情况：
- 1. 如果目标节点没有子节点，我们可以直接移除该目标节点。
- 2. 如果目标节只有一个子节点，我们可以用其子节点作为替换。
- 3. 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。
举例:(来源力扣)
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
首先找到需要删除的节点；
如果找到了，删除它。
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key < root.val) {
// 待删除节点在左子树中
root.left = deleteNode(root.left, key);
return root;
} else if (key > root.val) {
// 待删除节点在右子树中
root.right = deleteNode(root.right, key);
return root;
} else {
// key == root.val，root 为待删除节点
if (root.left == null) {
// 返回右子树作为新的根
return root.right;
} else if (root.right == null) {
// 返回左子树作为新的根
return root.left;
} else {
// 左右子树都存在，返回后继节点（右子树最左叶子）作为新的根
TreeNode successor = min(root.right);
successor.right = deleteMin(root.right);
successor.left = root.left;
return successor;
}
}
}
private TreeNode min(TreeNode node) {
if (node.left == null) {
return node;
}
return min(node.left);
}
private TreeNode deleteMin(TreeNode node) {
if (node.left == null) {
return node.right;
}
node.left = deleteMin(node.left);
return node;
}
}
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
return root;
}
if (root.val < key) {
root.right = deleteNode(root.right, key);
return root;
}
if (root.val == key) {
if (root.left == null && root.right == null) {
return null;
}
if (root.right == null) {
return root.left;
}
if (root.left == null) {
return root.right;
}
TreeNode successor = root.right;
while (successor.left != null) {
successor = successor.left;
}
root.right = deleteNode(root.right, successor.val);
successor.right = root.right;
successor.left = root.left;
return successor;
}
return root;
}
}
