代码随想录 -- 二叉树 -- 删除二叉搜索树中的节点

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

思路：

递归出口：

1. 当root为空时，返回空。

2. 当root的值和key相等时：

• root为叶子结点：返回空；
• root左孩子为空，右孩子不为空：返回root的右孩子；
• root右孩子为空，左孩子不为空：返回root的左孩子；
• root的左右孩子都不为空：找到root的右孩子的最左下节点，将root的左孩子连接在此节点，返回root的右孩子。

单层递归逻辑：

• 当root的值比key大，令root的左孩子等于递归root的左子树；
• 当root的值比key小，令root的右孩子等于递归root的右子树；
• 最后返回root。

class Solution(object):def deleteNode(self, root, key):if root==None:return Noneif root.val==key:if root.left==None and root.right==None:return Noneelif root.left!=None and root.right==None:return root.leftelif root.left==None and root.right!=None:return root.rightelse:cur=root.rightwhile cur.left!=None:cur=cur.leftcur.left=root.leftreturn root.rightif root.val>key:root.left=self.deleteNode(root.left,key)if root.val<key:root.right=self.deleteNode(root.right,key)return root