235. 二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
二叉搜索树找祖先就有点不一样了！| 235. 二叉搜索树的最近公共祖先_哔哩哔哩_bilibili
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点2和节点8的最近公共祖先是6。示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。
刚开始没什么想法，知道二叉搜索树的特点：中序遍历是有序数组。却不知道怎么用
看了卡哥题解：
把p、q和根节点比较：
①、当p、q都比根节点小时，说明pq都在左子树上，最近公共祖先也在左子树上，向左遍历
②、当p比根节点小，q比根节点大时，说明根节点即是pq的最近公共祖先
这里是用前序遍历，中序遍历还是后序遍历呢？因为这里不涉及中间节点的处理，所以其实前中后序遍历都行。
递归三部曲：
1、确定函数的参数和返回值：参数是当前节点以及两个目标节点。返回值是最近公共祖先。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
}2、确定终止条件：这里是不是遇到空节点就返回呢？其实都不需要，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。
3、确定单层递归的逻辑：遍历二叉树的时候将根节点的值与pq的值相比较，如果根节点的值大于pq的值，则向左遍历左子树的根节点；如果根节点小于pq的值，则向右遍历右子树的根节点；如果根节点介于pq之间，则说明根节点即是最近公共祖先，返回根节点：
if(root.value > p.value && root.value > q.value) return lowestCommonAncestor(root.left, p, q);
if(root.value < p.value && root.value < q.value) return lowestCommonAncestor(root.right, p, q);
return root;综合代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}701.二叉搜索树中的插入操作
701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
原来这么简单？ | LeetCode：701.二叉搜索树中的插入操作_哔哩哔哩_bilibili
if(root == null){
return new TreeNode(val);
}原来这么简单？ | LeetCode：701.二叉搜索树中的插入操作_哔哩哔哩_bilibili
这道题我一开始的想法就是把要插入的值和根节点比较，比根节点小就插入到根节点的右边，比根节点大就插入到根节点的左边。
递归三部曲：
1、确定参数和返回值：参数就是根节点以及要插入的元素，返回值就是插入元素后的根节点：
public TreeNode insertIntoBST(TreeNode root, int val){
}2、确定终止条件：当遇到空节点的时候，就把需要插入的元素插入，然后停止：
if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
return new TreeNode(val);3、确定单层递归的逻辑：比大小：
if(root.val < val){
root.right = insertIntoBST(root.right,val);
} else if(root.val > val){
root.left = insertIntoBST(root.left,val);
}
return root;综合代码：
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
return new TreeNode(val);
if (root.val < val){
root.right = insertIntoBST(root.right, val); // 递归创建右子树
}else if (root.val > val){
root.left = insertIntoBST(root.left, val); // 递归创建左子树
}
return root;
}
}450.删除二叉搜索树中的节点
450. 删除二叉搜索树中的节点 - 力扣（LeetCode）
调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点_哔哩哔哩_bilibili
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 1:
输入：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]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点示例 3:
输入: root = [], key = 0 输出: []提示:
- 节点数的范围
[0, 104].-105 <= Node.val <= 105- 节点值唯一
root是合法的二叉搜索树-105 <= key <= 105进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
如果删除的是叶子节点的话非常容易，但是如果删除的是根节点，就涉及到二叉树重新排序，比较复杂，暂时还没有想法。
看了卡哥的题解，一共有5种情况：
1、没找到需要删除的节点
2、找到了需要删除的节点且删除的是叶子节点，该叶子节点的左右子树都为空
3、找到了需要删除的节点且删除的节点的左子树为空，右子树不为空
4、找到了需要删除的节点且删除的节点的右子树为空，左子树不为空
5、找到了需要删除的节点且删除的节点左右子树都不为空
递归三部曲：
1、确定参数和返回值：参数是根节点和需要删除的值，返回值也是根节点：
public TreeNode deleteNode(TreeNode root, int key) {
}2、确定终止条件：删除值后终止。具体删除的时候又有5种情况：
①、没找到需要删除的值，返回根节点
if (root == null) return root;②、找到了需要删除的节点且删除的是叶子节点，该叶子节点的左子树为空,右子树不为空，则返回右子树
if(root.val == key){
if(root.left == null){
return root.right;
}
}③、找到了需要删除的节点且删除的节点的右子树为空，左子树不为空，则返回左节点
else if (root.right == null) {
return root.left;
} ④、找到了需要删除的节点且删除的节点左右子树都不为空：
例如要删除2：因为这是一棵二叉搜索树，所以2的左节点肯定比2的右节点的值小，那把2的左节点插入到哪里呢？应该把2的左节点插入到2的右节点的左子树上：
else {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
root = root.right;
return root;
}3、确定单层递归的逻辑：遍历寻找需要删除的节点。
如果当前节点的值大于要删除的节点值 key，则在当前节点的左子树中继续寻找要删除的节点；如果当前节点的值小于要删除的节点值 key，则在当前节点的右子树中继续寻找要删除的节点。
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
综合代码：
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
if (root.val == key) {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
root = root.right;
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
}