★【删除二叉搜索数节点】【递归】Leetcode 450. 删除二叉搜索树中的节点

---------------🎈🎈450. 删除二叉搜索树中的节点 题目链接🎈🎈-------------------

解法1 递归

有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
第五种情况示意图：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 删除操作分为五种情况（找到待删除元素即停止递归）
        // 1、删除节点不存在————return null
        // 2、删除的是叶子结点，左为空 右为空 ———— return null
        // 3、删除的节点 左为空 右不为空 ———— return root.right
        // 4、删除的节点，左不为空 右为空 ———— return root.left
        // 5、删除的节点，左不为空 右不为空
        //   ———— 找到需要删除节点的右子树的最左下角就是比他大一丢丢的元素temp，
        //   ———— 之后把删除节点的左子树移动到这个大一丢丢元素下面，temo.left=root.left
        //   ———— 最后删除节点：此时也就是左为空 右不为空，即return root.right

        // 停止条件（找到待删除的元素）
        if(root == null) return null;
        if(root.val == key){
            if(root.left == null && root.right ==null) return null;
            else if(root.left == null && root.right != null) return root.right;
            else if(root.left != null && root.right == null) return root.left;
            else{
                // 寻找这个待删除节点的右子树的最左边（就是比其大一丢丢的元素）
                TreeNode temp = root.right;
                while(temp.left != null){
                    temp = temp.left; 
                }
                // 将待删除的节点的左子树 转移到 temp的左子树位置
                temp.left = root.left;
                // 删除节点
                return root.right;
            }
        }
        
        // 递归思想：key大于当前root 就向右，key小于当前root 就向左。
        // 每一层接之后的返回
        root.left = deleteNode(root.left,key);
        root.right = deleteNode(root.right,key);
        return root;
    }
}    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38