代码随想录算法训练营第二十一天 | LeetCode 235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作、450. 删除二叉搜索树中的节点

1. LeetCode 235. 二叉搜索树的最近公共祖先

1.1 思路

1. 在普通二叉树中搜索最近公共祖先是用了后序遍历，然后一层一层返回。本题是二叉搜索树，可以利用它的特性，如果p和q都比根节点小，那说明最近公共祖先一定在左子树。如果p和q都比根节点大，那说明最近公共祖先一定在右子树。那找到了一个节点在p和q之间，那就是公共节点了，并且一定是最近的了，因为是二叉树，再往下不管是左还是右都分开了
2. 递归函数的参数和返回值：返回值就是节点，参数就是root，p，q。都是题目的
3. 终止条件：遇到空就返回空
4. 单层递归的逻辑：因为这题本来就是有序的，而且不涉及中间节点的处理，就不管前中后序了，只需要有左和右即可。如果root比p和q的都大，就向左搜索，left=travelsal(root.left, p, q），如果left不为空就说明left就是最近公共祖先了，就返回left。如果root比p和q的都小，就向右搜索，right=travelsal(root.right, p, q），如果right不为空就说明right就是最近公共祖先了，就返回right。剩下的情况就是最近公共祖先root在p和q之间了，就直接return root。

1.2 代码

//
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return root;
        }
        if(root.val>p.val&&root.val>q.val){
            TreeNode left=lowestCommonAncestor(root.left,p,q);
            if(left!=null){
                return left;
            }
        }
        if(root.val<p.val&&root.val<q.val){
            TreeNode right=lowestCommonAncestor(root.right,p,q);
            if(right!=null){
                return right;
            }
        }
        return root;
    }
}

2. LeetCode 701. 二叉搜索树中的插入操作

2.1 思路

1. 在二叉搜索树中插入任何一个节点的话，在叶子节点都能找到它的位置。所以是找到一个叶子节点插入即可，依然保持二叉树的有序性
2. 递归函数的参数和返回值：返回值节点node，参数就是root，val
3. 终止条件：如果遇到空，就找到插入节点的位置了，就是叶子节点了。就创建节点node然后放入val，然后返回node。因为是一层一层向下遍历，返回的时候就是把节点返回给上面遍历下来的那个节点
4. 单层递归的逻辑：如果节点值比val大，就向左遍历，就用root.left接收函数(root.left, val)的返回值，作为root的左孩子。如果节点值比val小，就向右遍历，就用root.right接收函数(root.right, val)的返回值，作为root的右孩子。举例这里如果递归到了最后一层的叶子节点，叶子节点插入的新节点就返回给此时的root，root就作为新节点的父节点，二叉树就连接起来了。最后return root；就是一层一层返回给最终新的二叉树的根节点了。

2.2 代码

//
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;
    }
}

3. LeetCode 450. 删除二叉搜索树中的节点

3.1 思路

1. 这题要求删除节点后依然保证仍是一棵二叉搜索树
2. 先分析有什么情况：①没找到要删的节点；其余四种情况就是找到了要删的节点②要删除的节点左右都为空，即这个节点是叶子节点；③这个节点不是叶子节点，左不为空右为空，就直接让其左孩子变为其父节点的左孩子；④这个节点不是叶子节点，左为空右不为空，就直接让其右孩子变为其父节点的右孩子；⑤左不为空右也不为空，这种情况需要大幅调整结构了。删除这个节点后要么就是让左孩子继位，要么就是让右孩子继位，举例假设让右孩子继位，左孩子就只能放在原右孩子的左子树中最左侧的位置（这个数是仅仅比被删节点大一点点的，就刚刚能让原左孩子作为这个节点的左孩子，这里可能不好理解，看视频的6分钟左右），放完以后，在删除节点以后，直接让被删除节点的父节点指向右孩子
3. 递归函数的返回值和参数：定义函数就是原题的函数，返回的是新的二叉搜索树的根节点
4. 终止条件：遍历找到要删除的节点。因为这题不需要遍历整棵二叉树，重点在删除节点的逻辑，因此删除的操作是放在终止条件中。
5. 第1种情况，就是遍历到空了也没找到，就返回null；
6. 第2种情况，是叶子节点(左右都为空)，就直接return null，这个null是由原节点的父节点接收，因为在代码最下面会有当前层的左子树=下一层递归的返回值以及右子树=下一层递归的返回值；
7. 第3种情况，左不为空右为空，就让被删节点的父节点接收其左孩子，就是返回root.left，被删节点的父节点会接收住的
8. 第4种情况，左为空右不为空，就让被删节点的父节点接收其右孩子，就是返回root.right，被删节点的父节点会接收住的
9. 第5种情况就else了，（已上面的例子以右孩子继位为例）先找到被删节点的右子树的最左侧的值，只有这个数是仅仅比被删节点大一点点的，（这里已经遍历到了被删节点）首先定义个cur=root.right，然后向左遍历去到叶子节点，while(cur.left!=null) cur=cur.left；然后让cur.left=root.left，即这个叶子节点的左子树等于被删节点的左子树了。然后就是删除那个节点了，此时的处理逻辑就是左为空右不为空（第4种情况）的处理逻辑了，就return root.right。如果是让左孩子继位就可以自己画图看看
10. 单层递归的逻辑：如果key<root.val就向左遍历搜索，root.left=delete(root.left, val)；如果key>root.val就向右遍历搜索，root.right=delete(root.right, val)；这里用节点的左右孩子接收的就是删除节点后返回的节点。最后左右子树处理完了就return root

3.2 代码

//
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;
  }
}