代码随想录——删除二叉搜索树中的节点（Leetcode450）

题目链接
在这里插入图片描述

递归

/**
 * 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) {
    	// 如果当前的节点是空的，那么二叉搜索树也是空的，因此返回null。
        if(root == null){
            return null;
        }
        // 如果当前节点的值大于要删除的键值（key），递归地在左子树中删除键值。
        if(root.val > key){
            root.left = deleteNode(root.left,key);
            return root;
        }
        // 如果当前节点的值小于要删除的键值，递归地在右子树中删除键值。
        if(root.val < key){
            root.right = deleteNode(root.right,key);
            return root;
        }
        // 如果找到了要删除的键值，这里有几种情况需要处理
        if(root.val == key){
        	// 如果该节点没有子节点，可以直接删除该节点
            if(root.left == null && root.right == null){
                return null;
            }
            // 如果该节点只有右子节点，可以将根节点替换为它的右子节点
            if(root.right == null){
                return root.left;
            }
            // 如果该节点只有左子节点，可以将根节点替换为它的左子节点
            if(root.left == null){
                return root.right;
            }
            // 如果该节点既有左子节点又有右子节点，需要找到右子树中的最小值（或最大值，因为BST的右子树只包含大于当前节点的值）节点，将其移动到当前节点的位置，然后删除那个最小值（或最大值）节点在右子树中的位置。
            TreeNode successor = root.right;
            // 为此，需要找到这个最小值（或最大值）节点的左子节点，并将它复制到当前节点的右子节点，然后删除这个最小值（或最大值）节点。这个步骤通过递归地在右子树中查找最小值节点来实现。在找到这个节点后，需要将这个节点的右子树连接到当前节点原来的右子节点上，同时将这个最小值（或最大值）节点的左子树连接到当前节点上。
            while(successor.left != null){
                successor = successor.left;
            }
            root.right = deleteNode(root.right,successor.val);
            successor.right = root.right;
            successor.left = root.left;
            return successor;
        }
        return root;
    }
}