第一题：235. 二叉搜索树的最近公共祖先

解题思路

1. 利用二叉搜索树的特性：
   二叉搜索树的特点是左子树的所有节点值都小于根节点值，右子树的所有节点值都大于根节点值。基于这个特性，我们可以通过比较根节点与要查找的两个节点 p 和 q 的值的大小关系，来确定最近公共祖先所在的子树方向。
2. 递归法思路：
   • 首先，比较根节点 root 的值和 p、q 的值大小。
   • 如果 root.val 大于 p.val 且大于 q.val，这意味着 p 和 q 都在 root 的左子树中，那么它们的最近公共祖先也必然在左子树，所以继续在左子树中递归调用 lowestCommonAncestor 方法去寻找。
   • 反之，如果 root.val 小于 p.val 且小于 q.val，说明 p 和 q 都在 root 的右子树中，就继续在右子树中递归查找。
   • 而当出现 root.val 的值介于 p.val 和 q.val 之间（或者等于其中某一个的值，因为节点也可以是它自己的祖先）时，此时这个 root 节点就是 p 和 q 的最近公共祖先，直接返回 root 即可。
3. 迭代法思路（代码中被注释部分）：
   和递归法类似，也是通过不断比较根节点与 p、q 的值大小来决定遍历方向。在一个 while 循环中，如果 root.val 大于 p.val 且大于 q.val，就将 root 指向其左子树节点（即 root = root.left）；如果 root.val 小于 p.val 且小于 q.val，就将 root 指向其右子树节点（即 root = root.right）；直到找到 root.val 介于 p.val 和 q.val 之间（或等于其中某一个值）的情况，此时跳出循环，返回这个 root 节点作为最近公共祖先。

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/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;// //迭代法// while(true){//     if(root.val > p.val && root.val > q.val){//         root = root.left;//     }else if(root.val < p.val && root.val < q.val){//         root = root.right;//     }else{//         break;//     }// }// return root;}
}

第二题：701.二叉搜索树中的插入操作

解题思路

1. 利用二叉搜索树特性确定插入位置：
   二叉搜索树的关键特性是左子树的所有节点值都小于根节点值，右子树的所有节点值都大于根节点值。基于此特性，要插入一个新值 val，我们就通过不断比较该值与当前节点（从根节点开始）值的大小关系，来决定新值应该插入到当前节点的左子树还是右子树中。
2. 递归思路：
   • 首先判断当前传入的根节点 root 是否为空。如果为空（意味着已经遍历到合适的位置可以插入新节点了），那就创建一个值为 val 的新节点并返回，这个新节点就是插入后的二叉搜索树的一部分了。
   • 接着，如果 root.val 小于 val，说明新值 val 应该插入到当前根节点的右子树中，那么就对右子树进行递归操作，也就是通过 root.right = insertIntoBST(root.right, val) 这句代码，以当前节点的右子节点作为新的 “根节点” 继续去判断新值 val 在这个右子树中的合适插入位置，不断重复这个过程，直到找到合适的空节点位置插入新值。
   • 反之，如果 root.val 大于 val，那就意味着新值 val 要插入到当前根节点的左子树中，通过 root.left = insertIntoBST(root.left, val) 对左子树进行递归查找合适的插入位置。
   • 最后，无论新值插入到了左子树还是右子树，最终都返回根节点 root，这样就能保证返回的是整个插入新值后的二叉搜索树的根节点，因为经过递归操作后，树的结构已经正确更新了。

代码 

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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.删除二叉搜索树中的节点

解题思路

1. 整体思路概述：
   要删除二叉搜索树中的指定节点并保持二叉搜索树的性质不变，需要先找到该节点，然后根据节点的不同情况（比如有无左子树、右子树等）来进行相应的删除操作，最后返回更新后的二叉搜索树的根节点。

2. 寻找要删除的节点：
   通过递归地比较当前节点 root 的值和要删除的 key 值的大小关系来查找目标节点。如果 root.val > key，说明要删除的节点可能在当前节点的左子树中，那就继续在左子树里递归查找，即执行 root.left = deleteNode(root.left, key)；同理，如果 root.val < key，则在右子树里递归查找，执行 root.right = deleteNode(root.right, key)。当 root.val == key 时，就意味着找到了要删除的节点，接下来要进行具体的删除操作。

3. 删除节点的不同情况处理：

   • 情况一：待删除节点没有左子树：
     此时直接返回该节点的右子树即可，因为这样就能将原节点从树中移除，并且保持二叉搜索树的性质，右子树中的节点原本就都大于原节点值，符合二叉搜索树的定义。
   • 情况二：待删除节点没有右子树：
     同理，直接返回该节点的左子树，左子树中的节点都小于原节点值，也能保证二叉搜索树性质不变。
   • 情况三：待删除节点既有左子树又有右子树：
     为了维持二叉搜索树的结构和性质，一种常见做法是用待删除节点右子树中的最小节点（也就是右子树中最左边的节点，它是右子树中值最小的，大于原节点左子树所有值）来替换待删除节点。具体操作就是先找到右子树中的最小节点 cur（通过不断访问左子节点来找到最左边的节点），然后将这个最小节点的左子树设置为待删除节点的左子树（因为这个最小节点原本没有左子树，且它大于原节点左子树的值，这样替换能保证二叉搜索树性质），最后让原节点指向其右子树（也就是用右子树整体替换掉原节点），并返回更新后的根节点。

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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;}
}