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

文章链接：二叉搜索树的最近公共祖先二叉搜索树的插入操作删除二叉搜索树中的节点

视频链接：二叉搜索树的最近公共祖先二叉搜索树的插入操作删除二叉搜索树中的节点

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

1.1 思路

1.2 代码

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

2.1 思路

2.2 代码

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

3.1 思路

3.2 代码

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

1.1 思路

在普通二叉树中搜索最近公共祖先是用了后序遍历，然后一层一层返回。本题是二叉搜索树，可以利用它的特性，如果p和q都比根节点小，那说明最近公共祖先一定在左子树。如果p和q都比根节点大，那说明最近公共祖先一定在右子树。那找到了一个节点在p和q之间，那就是公共节点了，并且一定是最近的了，因为是二叉树，再往下不管是左还是右都分开了
递归函数的参数和返回值：返回值就是节点，参数就是root，p，q。都是题目的
终止条件：遇到空就返回空
单层递归的逻辑：因为这题本来就是有序的，而且不涉及中间节点的处理，就不管前中后序了，只需要有左和右即可。如果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 思路

在二叉搜索树中插入任何一个节点的话，在叶子节点都能找到它的位置。所以是找到一个叶子节点插入即可，依然保持二叉树的有序性
递归函数的参数和返回值：返回值节点node，参数就是root，val
终止条件：如果遇到空，就找到插入节点的位置了，就是叶子节点了。就创建节点node然后放入val，然后返回node。因为是一层一层向下遍历，返回的时候就是把节点返回给上面遍历下来的那个节点
单层递归的逻辑：如果节点值比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 思路

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