450. 删除二叉搜索树中的节点(leetcode)

https://leetcode.cn/problems/delete-node-in-a-bst/

要点是确定函数语义,单层递归逻辑,确定好有返回值的这种写法,分析出5种情况,递归的时候接收好递归的返回的新树的根节点即可

class Solution {

    // 函数语义(单层递归逻辑):查找要删除的节点,并且返回删除节点后新的树的根节点
    public TreeNode deleteNode(TreeNode root, int key) {
        // 删除节点
        // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if(root==null)return null;
        if(root.val==key)
        {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if(root.left==root.right && root.left==null)return null;
            // 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
            else if(root.left==null && root.right!=null)return root.right;
            // 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if(root.right==null && root.left!=null)return root.left;
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。    
            else
            {
                TreeNode cur=root.right;
                while(cur.left!=null)cur=cur.left;
                cur.left=root.left;
                return root.right;
            }
        }
        // 不删除节点
        // 实现函数语义
        if(root.val > key)root.left=deleteNode(root.left,key);
        else root.right=deleteNode(root.right,key);
        return root;
    }
}